Research Interests
Computational Complexity
Algorithms
Hardness and Reductions
Meta-Complexity
Hardness Magnification
Current Research Directions
My current work investigates connections among recovery reductions, hardness magnification, meta-complexity, and barriers to complexity lower bounds. A recurring objective is to identify reductions and structural principles that convert seemingly modest computational hardness into stronger complexity-theoretic consequences.
Selected Publications
Recovery Reductions, Conjectures, and Barriers
Tejas Nareddy and Abhishek Mishra.
Electronic Colloquium on Computational Complexity, Report No. 157, 2025.
Introduces the random noise model and the notion of recovery reductions, in which a function must be recovered from a truth table corrupted on a randomly chosen fraction of inputs. The paper gives deterministic polynomial-time recovery reductions for a broad class containing many canonical NP-complete problems—including SAT, k-SAT, k-CSP, CLIQUE, and related problems—and also develops recovery reductions for Orthogonal Vectors and Parity k-Clique.
Structural and Spectral Properties of Corona Graphs
Rohan Sharma, Bibhas Adhikari, and Abhishek Mishra.
Discrete Applied Mathematics, 228, 14–31, 2017.
Studies a recursively generated family of graphs obtained by iterated corona products of a seed graph, viewed as a deterministic growing-network model. The paper derives structural properties including degree distribution, diameter, and betweenness distribution, and obtains adjacency, Laplacian, and signless Laplacian spectra for important classes of seed graphs.
Energy Efficient Voltage Scheduling for Multi-Core Processors with Software Controlled Dynamic Voltage Scaling
Abhishek Mishra and Anil Kumar Tripathi.
Applied Mathematical Modelling, 38(14), 3456–3466, 2014.
Studies minimum-energy voltage scheduling for multi-core processors with software-controlled dynamic voltage scaling and a finite set of discrete core speeds. The work formulates the scheduling problem mathematically, reduces it to an integer linear programming formulation, develops an exact scheduling algorithm, and reports energy improvements of up to 12.12% over the comparison method used in the experiments.