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.
Infographic:
Algorithms rule the world
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. Dr. Neeraj 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 attracting 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.
Bio
Dr. Neeraj Kayal is currently a Principal Researcher at the Microsoft Research lab in Bengaluru, where he has worked since 2008. Dr. Kayal works in the areas of complexity theory, algorithms, and related areas of theoretical computer science.
Neeraj Kayal was born in Guwahati, India. As an undergraduate student at IIT- Kanpur, Dr. Kayal in joint work with his advisor Prof. Manindra Agrawal and Dr. 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 Kayal received his Ph.D. from IIT-Kanpur and has held postdoctoral positions at the Institute for Advanced Study, Princeton and at DIMACS (Rutgers University). In 2012 he was awarded the Young Scientist Award from Indian National Science Academy (INSA). Dr. Kayal’s recent work has been focused on algorithms and lower bounds in algebraic complexity theory.
Timeline
Jury Citation
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.
Dr. Neeraj 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.
Dr. Neeraj Kayal reacts to winning the Infosys Prize
“I would like to congratulate Neeraj for winning the Infosys Prize 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.”
