Dr Neeraj Kayal is a much awarded computer scientist and mathematician, who has many feathers in his cap, the two most recent ones being the Shanti Swarup Bhatnagar Prize for Mathematical Sciences in 2022 and the Infosys Prize in Mathematical Sciences in 2021 for his contributions to Computational Complexity.
He graduated with a BTech from the Computer Science Department of the Indian Institute of Technology, Kanpur (IITK), in 2002, and the same year, along with Manindra Agrawal and Nitin Saxena introduced the AKS primality test, which garnered international attention and was featured in a report in The New York Times as well.
He earned his PhD in theoretical computer science from IIT-Kanpur in 2007 and conducted his postdoctoral studies at Rutgers University and the Princeton Institute for Advanced Study, USA. Since 2008, Dr Kayal has worked as Principal Researcher at the Microsoft Research Lab, Bengaluru.
In addition to creating effective algorithms for the reconstruction and equivalency of algebraic circuits, Dr Kayal has conducted a vast and inventive body of work on algebraic computation. This work involves the invention of deep lower bound approaches that demonstrate the limitations of this natural paradigm.
An algorithm is a set of instructions that facilitates the completion of a task. Algorithms in the context of computation are a series of instructions that specify what the computer should do. And how does one come up with an algorithm then? Even though mathematics is the language of algorithms, understanding algorithms only through mathematical means can be challenging. The study of the dynamics of complex systems, such as the human brain, the environment, and economies, is known as complexity theory. Complexity theory studies the operation of algorithms in computation.
One of the main issues in mathematics and computer science is proving that certain natural problems, like the well-known P vs. NP conundrum, need impractical amounts of computational power. The VP versus VNP dilemma, its algebraic manifestation, is likewise open-ended. Over the years, there has been very little advancement in the natural program of proving hardness for stronger and stronger models for both. Some of the advances made in this direction can be attributed to Dr Kayal’s novel and revolutionary proving procedures. In addition to the evident mathematical benefit of bolstering our meagre toolkit to tackle these issues, his work has had a significant psychological impact by igniting interest in this challenging field of study and drawing in younger researchers.
Dr Kayal is a specialist in algebraic complexity theory, a branch of mathematics that studies the most elegant methods for the most effective solution of computing problems. Dr Kayal made fundamental contributions to lower bounds, which are among his contributions to algebraic complexity theory. Computational lower bounds are fundamental principles that acknowledge that a task can only be solved with a minimum number of resources, including memory, running time, and communication. Lower bounds bear resemblance to physical rules, such as the energy conservation law.
Dr Kayal was a member of a group that developed an algorithm to quickly determine whether a given integer was prime. In a problem that has intrigued mathematicians since the dawn of time, this was a momentous development. Checking for primality is crucial in a world where algorithms are in charge. For instance, the RSA algorithm is a method that is necessary for safe online transactions. An RSA algorithm’s level of security is based on how challenging it is to determine a number’s prime factors. The work of Dr Kayal has broader implications in domains including statistics, cryptography, and theoretical computer science, where it can be used to solve challenging problems.
The IITK bestowed upon Dr Kayal the Distinguished Alumnus Award in 2003 in recognition of his contributions to computational complexity theory. In the year 2006, he was also bestowed with the Fulkerson Prize and Godel Prize. The Indian National Science Academy (INSA) presented him with the Young Scientist Award in 2012 in recognition of his contributions to the field of arithmetic complexity theory. These contributions included the creation of a reconstruction algorithm for arithmetic formulas, a deterministic algorithm for primality testing, and a solution to the constant fan-in conjecture for depth three circuits.
