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

Isomorphism Conjecture

Structure of NP-complete Degree

Complete Degrees under AC^0 Reductions

Complete Degrees under 1-L and 1-NL Reductions

Complete Degrees under other Weak Reductions

Hybrid Systems

Problems in NC

Problems in NP and Higher Classes


  • 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.