Manindra Agrawal

PhD (IIT Kanpur)

Professor, Department of Computer Science and Engineering


Research Interest



  • PhD (Computer Science), IIT Kanpur, 1991 .
    Thesis Title: Towards a Characterization of NP-Complete Sets
    Supervisor: Somenath Biswas
  • B.Tech (Computer Science), IIT Kanpur, 1986



Algorithms, Complexity Theory, Computational Number Theory and Algebra, Cryptography

  • PRIMES is in P, Annals of Mathematics, 160(2), 781-793, 2004
  • Primality and Identity Testing via Chinese Remaindering, Journal of the ACM, 50(4), 429-443, 2003
  • The Isomorphism Conjecture for Constant Depth Reductions, Journal of Comp and Sys Sci, 77(1), 3-13, 2011
  • Arithmetic Circuits: A Chasm at Depth Four, proceedings of 49th Foundations of Computer Science (FOCS), 48-53, 2008
  • Quasi-polynomial hitting sets for set depth-D formulas, proceedings of Symposium on Theory of Computation (STOC), 321-330, 2013
  • Designed encryption algorithms for Indian Navy and Indian Air Force, 1998-2008

Designed the first efficient and deterministic algorithm for testing if a number is prime.
Nitin Saxena, Satyadev Nandkumar

  • Fellow, School of Mathematics, SPIC Science Foundation, Chennai, 1993-95
  • Humboldt Fellow, University of Ulm, Germany, 1995-96

  • Department of Computer Science and Engineering, IIT Kanpur, 1996-present

  • Padma Shri, 2013.
  • Infosys Prize, 2008
  • Godel Prize, 2006
  • Shanti Swarup Bhatnagar Award, 2003
  • Clay Research Award, 2002
  • S S Bhatnagar Award, 2003


Department of Computer Science and Engineering
IIT Kanpur,
Kanpur 208016

Office Phone: 0512-259-7338 (O)

Email: [AT]

Complexity Theory, Theory of Computation, Cryptography, Number Theory


Birds at IIT Kanpur
Information for School Children
IITK Radio
Counseling Service