Prof. Dr. Nitin Saxena

Former Bonn Junior Fellow
Current position: Associate Professor, Indian Institute of Technology IIT Kanpur, India

E-mail: nitin.saxena(at)
Institute: Mathematical Institute
Institute of Computer Science
Research Areas: Research Area KL
Former Research Area K
Former Research Area L
Date of birth: 03.May 1981
Mathscinet-Number: 754832

Academic Career


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

Research Profile

My favorite problems are - polynomial identity testing (PIT) and polynomial factoring.

Depth-3 PIT. I have found the (currently) best known solution for depth-3 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-3 completely.

Depth-4 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 hitting-set 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 m-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 m-schemes (which are themselves a generalization of finite groups).

Research Projects and Activities

Structural and algorithmic complexity

Contribution to Research Areas

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 VP<br>neVNP question (the algebraic version of the P<br>neNP question!). I have been able to solve several of its cases, but a lot remains to be done in the future.

Selected Publications

[1] Nitin Saxena
Progress on polynomial identity testing
Bull. Eur. Assoc. Theor. Comput. Sci. EATCS (99): 49--79
[6] Nitin Saxena
Diagonal circuit identity testing and lower bounds
Automata, languages and programming. Part I
of Lecture Notes in Comput. Sci. : 60--71
Publisher: Springer, Berlin
DOI: 10.1007/978-3-540-70575-8_6

Publication List



Distinguished Alumnus Award of IIT Kanpur, India


IBM Outstanding PhD Student Award


AMS-MPS Delbert Ray Fulkerson Prize


Gödel Prize


Best Paper Award in Complexity Conference (CCC 2006)


Best Paper Award in ICALP (2011) Conference

Selected Invited Lectures


Indocrypt, Hyderabad, India


Dutch Theory Day, Utrecht, Netherlands


Algorithmic Number Theory, Turku, Finland


Complexity Theory at Oberwolfach, Germany


Computational Complexity at Dagstuhl, Germany


EURO Operational Research, Bonn, Germany


Computational Complexity at Dagstuhl, Germany


ICM Satellite Workshop, Bangalore, India


Number Theory Workshop, Warsaw, Poland


MPI für Informatik, Saarbrücken, Germany

Selected PhD students

Johannes Mittmann (2013): “Independence in Algebraic Complexity Theory” (Approaches to polynomial identity testing)

Manuel Arora (2013): “Extensibility of Association Schemes and GRH-Based Deterministic Polynomial Factoring” (Studying m-schemes & polynomial factoring)

Supervised Theses

  • Diplom theses: 6, currently 4
  • PhD theses: 2, currently 2
Download Profile