Publications
Surveys
The Isomorphism Conjecture for NP. Computability in Context: Computation and Logic in the Real World, Eds: Barry Cooper and Andrea Sorbi, World Scientific, 2011.
Classifying Polynomials and Identity Testing (with Ramprasad Saptharishi). Current Trends in Science (Platinum Jubilee Special, Indian Academy of Sciences), 2009.
Primality Testing Based on Fermat's Little Theorem. ICDCN 2006.
Determinant verus Permanent. ICM 2006.
Proving Lower Bounds via Pseudo-Random Generators. FSTTCS 2005.
Automorphisms of Finite Rings and Applications to Complexity of Problems (with Nitin Saxena). STACS 2005.
Computational Number Theory and Algebra
Yoshinori Aono, Manindra Agrawal, Takakazu Satoh, Osamu Watanabe, On the Optimality of Lattices for the Coppersmith Technique, Applied Algebra in Engineering, Communication and Computing 29(2), 169--195, 2018. Conference version here.
Manindra Agrawal, Nitin Saxena, Shubham Srivastava, Integer Factoring Using Small Algebraic Dependencies, MFCS, 6:1-6:14, 2016.
Manindra Agrawal, Nitin Saxena, Equivalence of F-algebras and Cubic Forms, STACS, LNCS 3884: 115-126, 2006.
Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P, Annals of Mathematics 160(2): 781-793, 2004. The original version of the paper is here.
Manindra Agrawal, Somenath Biswas, Primality and Identity Testing via Chinese Remaindering, Journal of the ACM 50(4): 429-443, 2003.
Derandomization and PIT
Manindra Agrawal, Sumanta Ghosh, Nitin Saxena, Bootstrapping Variables in Algebraic Circuits, PNAS 116(17): 8107-818, 2019.
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits, SIAM Journal of Computing 45(4), 1533-1562, 2016. Conference version here.
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena, Hitting Sets for ROABP and Sum of Set-Multilinear Circuits, SIAM Journal of Computing 44(3), 669-697, 2015.
Manindra Agrawal, Chandan Saha, Nitin Saxena, Quasi-polynomial hitting sets for set depth-D formulas, STOC 2013: 321-330.
Manindra Agrawal, V Vinay, Arithmetic Circuits: A Chasm at Depth Four, FOCS 2008.
Manindra Agrawal, On Derandomization Tests for Certain Polynomial Identities, Invited Talk at CCC 2003: 355-359.
Manindra Agrawal, Hard Sets and Pseudo-random Generators for Constant Depth Circuits, FSTTCS 2001, LNCS 2245: 58-69.
Isomorphism Conjecture
Structure of NP-complete Degree
Manindra Agrawal, Osamu Watanabe, One-Way Functions and the Berman-Hartmanis Conjecture. CCC 2009.
Manindra Agrawal, Pseudo-random Generators and the Structure of Complete Degrees, CCC 2002: 139-146.
Complete Degrees under AC^0 Reductions
Manindra Agrawal, The Isomorphism Conjecture for Constant Depth Reductions, JCSS 77 (special issue on Karp's Kyoto Prize): 3-13, 2011.
Manindra Agrawal, The First-Order Isomorphism Theorem, FSTTCS 2001, LNCS 2245: 70-82.
Manindra Agrawal, Towards Uniform AC^0-Isomorphisms, CCC 2001: 13-20.
Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich, Reducing the complexity of reductions, Computational Complexity 10(2): 117-138, 2001.
Manindra Agrawal, Eric Allender, Steven Rudich, Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem, JCSS 57: 127-143, 1999.
Complete Degrees under 1-L and 1-NL Reductions
Manindra Agrawal, On the Isomorphism Conjecture for Weak Reducibilities, JCSS 53(2): 267-282, 1996.
Manindra Agrawal, Somenath Biswas, Polynomial Isomorphism of 1-L Complete Sets, JCSS 53(2): 155-160, 1996.
Manindra Agrawal, DSPACE(n) ?= NSPACE(n): A Degree Theoretic Characterization, JCSS 54(3): 383:392, 1997.
Complete Degrees under other Weak Reductions
Manindra Agrawal, For completeness, sublogarithmic space is no space, Information Processing Letters 82(6): 321-325, 2002.
Manindra Agrawal, S Venkatesh, On the Isomorphism Conjecture for 2DFA Reductions, Intl Journal on Foundations of Computer Science 7(4): 339-352, 1996.
Hybrid Systems
S Akshay, Manindra Agrawal, B Genest, P S Thiagarajan, Approximate Verification of the Symbolic Dynamics of Markov Chains, JACM 62(1), 2.1-2.34, 2015.
S Akshay, Manindra Agrawal, B Genest, P S Thiagarajan, Verification of the Symbolic Dynamics of Markov Chains, LICS 2012: 55-64.
Manindra Agrawal, Frank Stephan, P S Thiagarajan, Shaofa Yang, The Discrete Time Behavior of Restricted Linear Hybrid Automata, Modern Applications of Automata Theory (World Scientific): 437-453, 2012.
Manindra Agrawal, Frank Stephan, P S Thiagarajan, Shaofa Yang, Behavioural Approximations for Restricted Linear Differential Hybrid Automata, HSCC 2006, LNCS 3927: 4–18.
Manindra Agrawal, P S Thiagarajan, The Discrete Time Behavior of Lazy Linear Hybrid Automata, HSCC 2005, LNCS 3414: 55–69.
Manindra Agrawal, P S Thiagarajan, Lazy Rectangular Hybrid Automata, HSCC 2004, LNCS 2993: 1–15.
Problems in NC
Manindra Agrawal, T M Hoang, Thomas Thierauf, The Polynomially Bounded Perfect Matching Problem is in NC^2, STACS 2007, LNCS 4393: 489-499.
Manindra Agrawal, Eric Allender, Samir Datta, On TC^0, AC^0, and Arithmetic Circuits, JCSS 60(2): 395-421, 2000.
Manindra Agrawal, Thomas Thierauf, "The Satisfiability Problem for Probabilistic Ordered Branching Programs", Theory of Computing Systems 34: 471-487, 2001.
Manindra Agrawal, Eric Allender, Samir Dutta, H Vollmer, C Wagner, Characterizing Small Space and Small Depth Classes by Operators of Higher Types, Chicago Journal on Theoretical Computer Science, 2000.
Problems in NP and Higher Classes
Manindra Agrawal, Thomas Thierauf, "The Formula Isomorphism Problem", SIAM J. Comput. 30(3): 990-1009, 2000.
Manindra Agrawal, V Arvind, A Note on Decision versus Search for Graph Automorphism, Information and Computation 131(2): 179–189, 1996.
Manindra Agrawal, Somenath Biswas, NP-creative Sets : A New Class of Creative Sets in NP, Mathematical Systems Theory 29: 487–505, 1996.
Manindra Agrawal, V Arvind, Quasi-linear Truth-table Reductions to P-selective Sets, Theoretical Computer Science 158: 361–370, 1996.
Manindra Agrawal, Richard Beigel, Thomas Thierauf, Pinpointing Computation with Modular Queries in the Boolean Hierarchy, FSTTCS 1996, LNCS 1180: 322–334.
Manindra Agrawal, Somenath Biswas, Universal Relations, CCC 1992: 207–220.
Miscellaneous
Manindra Agrawal, Diptarka Chakravarty, Satyadev Nandkumar, Dimension, Pseudorandomness and Extraction of Pseudorandomness, Computability 6(3), 277-305, 2017.
P Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, K G Larsen, Kurt Mehlhorn, The Query Complexity of Finding a Hidden Permutation, Discrete Applied Mathematics 260, 28-50, 2019.