Profile
Profile

Prof. Dr. Nitin Saxena

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

E-mail: nitin.saxena(at)gmail.com
Homepage: http://www.cse.iitk.ac.in/users/nitin/
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

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

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
2009
[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
2008
DOI: 10.1007/978-3-540-70575-8_6

Publication List

Awards

2003

Distinguished Alumnus Award of IIT Kanpur, India

2005

IBM Outstanding PhD Student Award

2006

AMS-MPS 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

Selected Invited Lectures

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

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