Quick Links
Nitin Saxena
PhD (IIT Kanpur)
Associate Professor, Department of Computer Science and Engineering
Research Interest
Computational Complexity Theory, Algebra, Algebraic Geometry.
Office
RM-203,
Department of Computer Science and Engineering
IIT Kanpur,
Kanpur 208016
Specialization
Theoretical Computer Science
Education
PhD, (IIT Kanpur), 2006
B.tech, (IIT Kanpur), 2002
Selected Publications
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits'' (with Manindra Agrawal, Chandan Saha and Ramprasad Saptharishi), 44th ACM Symposium on Theory of Computing (STOC), pp.599-614, 2012. [Invited in the special issue of SICOMP.]
Algebraic independence and blackbox identity testing'' (with Malte Beecken and Johannes Mittmann), 38th International Colloquium on Automata, Languages and Programming (ICALP), pp.137-148, 2011.[Awarded the Best Paper in Track A. Invited & published in the special issue of Inform. Comput.]
Blackbox identity testing for bounded top fanin depth-3 circuits: The field doesn't matter'' (with C.Seshadhri), 43rd STOC, pp.431-440, 2011.[Invited & published in the special issue of SICOMP.]
Polynomial identity testing for depth 3 circuits'' (with Neeraj Kayal), 21st IEEE Conference on Computational Complexity (CCC), pp.9-17, 2006. [Awarded the Best Paper and Best Student Paper Awards. Invited & published in the special issue of Comp. Complex.]
PRIMES is in P'' (with Manindra Agrawal and Neeraj Kayal),Annals of Mathematics, vol.160(2), 781-793, 2004. [Awarded Goedel Prize 2006 and Fulkerson Prize 2006.]
Awards & Fellowships
Best Paper at ICALP Conference – 2011. Awarded by EATCS the Best Paper Award (Track A) for the joint paper ``Algebraic independence and blackbox identity testing''.
IEEE Conference on Computational Complexity Awards -- 2006 . Awarded both the Best Paper Award and the Ronald V. Book Best Student Paper Award for the joint paper ``Polynomial Identity Testing for Depth 3 Circuits''.
Goedel Prize – 2006. Awarded by ACM-SIGACT & EATCS for the joint paper ``PRIMES is in P''.
Fulkerson Prize – 2006. Awarded by AMS & MPS for the joint paper ``PRIMES is in P''.
Distinguished Alumnus Award of IIT Kanpur -- 2003 . Global Indus Technovators Awards – 2003.