1. Home
  2. Research
  3. Publications
  4. Presentation
  5. Group
  6. Department

Personal Details

Designation : Adjunct Professor Department : Mathematics E-Mail : manindra@iitk.ac.in Phone : , - Fax : +91 755 669 2392



    Survey


    • Automorphisms of Finite Rings and Applications to Complexity of Problems (with Nitin Saxena). STACS 2005.
    • Determinant verus Permanent. ICM 2006. Proving Lower Bounds via Pseudo-Random Generators. FSTTCS 2005
    • Determinant verus Permanent. ICM 2006
    • Classifying Polynomials and Identity Testing (with Ramprasad Saptharishi). Current Trends in Science (Platinum Jubilee Special, Indian Academy of Sciences), 2009.
    • The Isomorphism Conjecture for NP. Computability in Context: Computation and Logic in the Real World, Eds: Barry Cooper and Andrea Sorbi, World Scientific, 2011.

    Computational Number Theory and Algebra


    • Manindra Agrawal, On Derandomization Tests for Certain Polynomial Identities, Invited Talk at CCC 2003: 355-359
    • Manindra Agrawal, Somenath Biswas, Primality and Identity Testing via Chinese Remaindering, Journal of the ACM 50(4): 429-443, 2003.
    • 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, Nitin Saxena, Equivalence of F-algebras and Cubic Forms, STACS, LNCS 3884: 115-126, 2006.
    • Manindra Agrawal, V Vinay, Arithmetic Circuits: A Chasm at Depth Four, FOCS 2008.

    Derandomization


    • Manindra Agrawal, Osamu Watanabe, One-Way Functions and the Berman-Hartmanis Conjecture. CCC 2009
    • Manindra Agrawal, Hard Sets and Pseudo-random Generators for Constant Depth Circuits, FSTTCS 2001, LNCS 2245: 58-69.

    Isomorphism Conjecture


    Likely Structure of NP-complete Degree


    • Manindra Agrawal, Pseudo-random Generators and the Structure of Complete Degrees, CCC 2002: 139-146.
    • Manindra Agrawal, The Isomorphism Conjecture for Constant Depth Reductions, JCSS 77 (special issue on Karp-s Kyoto Prize): 3-13, 2011.

    Complete Degrees Under AC^0 Reductions


    • Manindra Agrawal, On the Isomorphism Conjecture for Weak Reducibilities, JCSS 53(2): 267-282, 1996
    • Manindra Agrawal, Eric Allender, Steven Rudich, Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem, JCSS 57: 127-143, 1999.
    • Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich, Reducing the complexity of reductions, Computational Complexity 10(2): 117-138, 2001.
    • Manindra Agrawal, Towards Uniform AC^0-Isomorphisms, CCC 2001: 13-20.
    • Manindra Agrawal, The First-Order Isomorphism Theorem, FSTTCS 2001, LNCS 2245: 70-82.

    Complete Degrees Under 1-L and 1-NL Reductions


    • Manindra Agrawal, For completeness, sublogarithmic space is no space, Information Processing Letters 82(6): 321-325, 2002.
    • Manindra Agrawal, DSPACE(n) ?= NSPACE(n): A Degree Theoretic Characterization, JCSS 54(3): 383:392, 1997.
    • Manindra Agrawal, Somenath Biswas, Polynomial Isomorphism of 1-L Complete Sets, JCSS 53(2): 155-160, 1996