

2006  PhD, Indian Institute of Technology (IIT) Kanpur, India  2006  2008  Scientific Researcher, Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands  2008  2013  Professor (W2, Bonn Junior Fellow), University of Bonn  Since 2013  Associate Professor, Indian Institute of Technology (IIT) Kanpur, India 


My favorite problems are  polynomial identity testing (PIT) and polynomial factoring.
Depth3 PIT. I have found the (currently) best known solution for depth circuits. This has led to a series of interesting algebraic results [2,3,4]. I would like to further these approaches and solve the case of depth completely.
Depth4 PIT. This case is known to be almost as hard as the general PIT. I have investigated several approaches here, leading to many partial solutions [5,6]. I think these methods are quite deep and their further investigation would not only improve the state of PIT but also make commutative algebra theory more effective.
Determinant PIT. Certain computational graph problems, like matching, could be expressed as PIT of a determinant polynomial. I have some partial results in this kind of PIT [7]. In the future I would like to make these algorithms blackbox, i.e. find a hittingset for symbolic determinants. This would show, for example, that matching has efficient parallel algorithms (currently, a big open question).
The problem of polynomial factorization over finite fields is another classical question that has no known efficient deterministic algorithms [8].
Schemes Conjecture. I have shown that under GRH and under a natural conjecture about the structure of combinatorial schemes, polynomial factoring can be solved efficiently [9]. I would like to investigate this conjecture in the future. The long term goal of this research is to develop a representation theory for schemes (which are themselves a generalization of finite groups).


Structural and algorithmic complexity


Former Research Area L My research focuses on computational algebra algorithms and understanding classical computation by applying algebraic techniques. Specifically, I have found algorithms for primality testing, polynomial factoring and polynomial identity testing (PIT).
Amongst these, PIT is the most fundamental in complexity theory [1], as even a partial solution to it would resolve the VPVNP question (the algebraic version of the PNP question!). I have been able to solve several of its cases, but a lot remains to be done in the future. 


[ 1] Nitin Saxena
Progress on polynomial identity testing Bull. Eur. Assoc. Theor. Comput. Sci. EATCS (99): 4979 2009[6] Nitin Saxena
Diagonal circuit identity testing and lower bounds Automata, languages and programming. Part I of Lecture Notes in Comput. Sci. : 6071 Publisher: Springer, Berlin 2008




2003  Distinguished Alumnus Award of IIT Kanpur, India  2005  IBM Outstanding PhD Student Award  2006  AMSMPS Delbert Ray Fulkerson Prize  2006  Gödel Prize  2006  Best Paper Award in Complexity Conference (CCC 2006)  2011  Best Paper Award in ICALP (2011) Conference 


2002  Indocrypt, Hyderabad, India  2007  Dutch Theory Day, Utrecht, Netherlands  2007  Algorithmic Number Theory, Turku, Finland  2007  Complexity Theory at Oberwolfach, Germany  2007  Computational Complexity at Dagstuhl, Germany  2009  EURO Operational Research, Bonn, Germany  2009  Computational Complexity at Dagstuhl, Germany  2010  ICM Satellite Workshop, Bangalore, India  2010  Number Theory Workshop, Warsaw, Poland  2011  MPI für Informatik, Saarbrücken, Germany 


Johannes Mittmann (2013): “Independence in Algebraic Complexity Theory” (Approaches to polynomial identity testing)
Manuel Arora (2013): “Extensibility of Association Schemes and GRHBased Deterministic Polynomial Factoring” (Studying schemes & polynomial factoring)


 Diplom theses: 6, currently 4
 PhD theses: 2, currently 2


Download Profile 