Mathematics, 2021

Neeraj Kayal

Principal Researcher, Microsoft Research, Bengaluru, India

The Infosys Prize in Mathematics for 2021 is awarded to Neeraj Kayal of Microsoft Research, Bangalore, for his outstanding contributions to Computational Complexity. In particular, Kayal’s extensive, innovative work on algebraic computation includes the development of deep lower bound techniques proving limitations of this natural model, as well as designing efficient algorithms for reconstruction and equivalence of such algebraic circuits.

Bio

Neeraj Kayal is currently a Principal Researcher at the Microsoft Research lab in Bangalore, India, where he has worked since 2008. Neeraj works in the areas of complexity theory, algorithms, and related areas of theoretical computer science.

Neeraj was born in Guwahati, India. As an undergraduate student at IIT, Kanpur, Neeraj in junta work with his advisor Manindra Agrawal and Nitin Saxena, discovered the first deterministic polynomial time algorithm for primality testing. Their work won the authors the Godel Prize (2006) and the Fulkerson prize (2006). Neeraj received his Ph.D. from IIT Kanpur and has held postdoctoral positions at the Institute for Advanced Study and at DIMACS (Rutgers University). In 2012 he was awarded the Young Scientist Award from INSA (Indian National Science Academy). Neeraj’s recent work has been focused on algorithms and lower bounds in algebraic complexity theory.

Scope and impact of work

Proving that some natural problems require infeasible computational resources, exemplified by the famous P vs. NP question, is a major problem of mathematics and computer science. Its algebraic incarnation, the VP vs. VNP question, is equally wide open. For both, the natural program of proving hardness for stronger and stronger models, has seen extremely slow progress over the decades. Kayal’s new proof techniques are responsible for some of the leaps in this progress, significantly transforming the state-of-art. Beyond the obvious mathematical impact of adding powerful tools to the small arsenal we have to attack these problems, his work has had an important psychological effect, injecting enthusiasm (and young people) into this difficult research area. Indeed, both his research and his mentoring of young students and postdocs in India, are central to India’s leading presence in this field.

Citation by the Jury

Numerous computational problems, arising both in the sciences and in industry, are inherently algebraic, namely manipulating elements of some underlying field. These include the solution of linear and polynomial systems of equations, the computation of natural polynomials like the determinant and natural transformations like the Fourier transform, and many others. Designing efficient algebraic programs or circuits for such problems is extremely important, as is understanding the limitations of this computational model.

Kayal has made foundational contributions to both areas, focusing on lower bounds, the holy grail of computational complexity, namely showing that some natural problems cannot be solved by too small or too simple circuits. Towards this end he designed new ingenious proof techniques, some based on algebraic-geometric intuition, to prove such limitations, as well as efficiently uncover the structure of unknown circuits from their input-output behavior.

Congratulatory message from the Jury Chair

“I would like to congratulate Neeraj for winning the Infosys Prize for 2021. Neeraj’s deep work in theoretical computer science tackles the hardest problems in the field. His work in algebraic complexity theory has been very impactful, and forges new connections with classical mathematical fields like Number Theory and Algebraic Geometry. He has worked with many of his young colleagues and senior researchers in India, making the country an important center in the field of algebraic complexity.”