Fact-checked by Grok 2 weeks ago

Neeraj Kayal

Neeraj Kayal is an Indian computer scientist and mathematician renowned for co-authoring the AKS primality test, the first deterministic algorithm that proves whether a given number is prime in polynomial time relative to the number of digits in the number.^[1] This breakthrough, developed with Manindra Agrawal and Nitin Saxena during his doctoral studies, resolved a long-standing open problem in computational number theory by placing the PRIMES decision problem in the complexity class P.^[1] Kayal's work has had profound implications for algorithmic number theory and theoretical computer science, earning widespread recognition for its elegance and efficiency.^[2] Born in Guwahati, India, Kayal completed both his B.Tech. and Ph.D. in computer science at the Indian Institute of Technology Kanpur between 2002 and 2006, with his doctoral thesis advised by Manindra Agrawal and focusing on algorithmic number theory and algebraic complexity.^[2] Following his Ph.D., he held postdoctoral positions at the Institute for Advanced Study in Princeton and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University, where he further explored intersections of algebra, geometry, and complexity theory.^[2] These early experiences laid the foundation for his expertise in developing novel proof techniques for problems like distinguishing between polynomial-time computable and verifiable arithmetic circuits.^[2] Since 2008, Kayal has served as a Principal Researcher at Microsoft Research Lab in Bangalore, India, where he investigates problems at the crossroads of computational complexity, algebra, number theory, and geometry.^[3] His research emphasizes algebraic complexity theory, including lower bound techniques for arithmetic circuits and efficient algorithms for algebraic computation, with applications to broader questions in theoretical computer science such as the VP versus VNP problem.^[2] Kayal has also contributed to mentoring young researchers in India through initiatives in theoretical computer science.^[2] Kayal's contributions have been honored with several prestigious awards, including the 2006 Gödel Prize and Fulkerson Prize, shared with Agrawal and Saxena for the AKS primality test. In 2012, he received the Young Scientist Award from the Indian National Science Academy, and in 2021, the Infosys Prize in the Mathematical Sciences for advancing algebraic complexity theory.^[2] Most recently, he was awarded the Shanti Swarup Bhatnagar Prize in Mathematical Sciences for 2022, recognizing his significant advancements in algorithms for algebra and number theory, as well as innovative techniques in arithmetic complexity.^[4]

Early life and education

Early life

Neeraj Kayal was born in Guwahati, Assam, India, and spent his childhood there.^[2] From a young age, Kayal displayed a strong interest in mathematics and science, particularly numbers.^[5] This passion led him to participate in mathematics competitions, including representing India at the International Mathematical Olympiad in 1997.^[6] His time at Cotton College in Guwahati further nurtured these interests.^[5] These formative experiences in Guwahati inspired Kayal's transition to higher education at IIT Kanpur, where he pursued studies in computer science.^[5]

Education

Neeraj Kayal completed his B.Tech. in Computer Science from the Indian Institute of Technology Kanpur (IIT Kanpur) in 2002.^[7] His undergraduate education at IIT Kanpur provided a strong foundation in computer science, where he demonstrated early aptitude for theoretical aspects of the field. During this period, Kayal participated in research projects under the supervision of Manindra Agrawal, exploring topics in algorithmic number theory as part of his B.Tech. thesis work.^[8] Kayal pursued his graduate studies at the same institution, earning a Ph.D. in Theoretical Computer Science from IIT Kanpur in 2007, with Manindra Agrawal serving as his advisor.^[7]^[9] His doctoral research centered on algorithms and complexity theory, with a particular emphasis on derandomization techniques for problems in number theory and algebraic computation.^[10] The Ph.D. thesis titled Derandomizing Some Number-Theoretic and Algebraic Algorithms.^[9] This work built on his undergraduate research involvement, deepening his expertise in deterministic approaches to traditionally randomized computational challenges.^[11]

Professional career

Early academic positions

Following the completion of his PhD at the Indian Institute of Technology Kanpur in 2006, Neeraj Kayal took up a postdoctoral fellowship at the Institute for Advanced Study (IAS) in Princeton, New Jersey.^[2] He served as a member of the School of Mathematics there from September 2006 to August 2007, overlapping with the final stages of his doctoral work and allowing him to build on his expertise in theoretical computer science under the mentorship of Avi Wigderson. During this period, Kayal focused on algebraic aspects of computational complexity, including collaborations on techniques like partial derivatives for analyzing arithmetic circuits. Subsequently, from 2007 to 2008, Kayal held a postdoctoral position at Rutgers University through the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), where he continued his research in complexity theory.^[12] At Rutgers, he worked with faculty such as Eric Allender, engaging in projects related to the boundaries between algebra and computability in theoretical computer science.^[13] These early academic roles provided Kayal with an environment to refine his skills in algebraic complexity before transitioning to industry research. In 2008, he joined Microsoft Research Lab in Bangalore as a researcher.^[2]

Career at Microsoft Research

Neeraj Kayal joined the Microsoft Research Lab India in Bengaluru in 2008 as a researcher, following postdoctoral positions at the Institute for Advanced Study in Princeton and DIMACS at Rutgers University.^[2] His initial role focused on advancing theoretical computer science within the lab's algorithms and complexity group.^[3] Over the years, Kayal advanced to the position of Principal Researcher, which he holds as of 2025, reflecting his sustained contributions to the lab's research agenda.^[3] In this capacity, he has been actively involved in Microsoft Research India's initiatives exploring computational complexity and its interdisciplinary applications, including connections to machine learning and algebraic methods.^[14] These efforts are part of broader collaborative programs, such as the Microsoft India Research Initiative, where he works alongside other MSR researchers on foundational problems with practical implications.^[15] Kayal has also engaged in mentorship and internal collaborations at Microsoft Research India, guiding young researchers and students through seminars, podcasts, and joint projects with colleagues like Ravishankar Krishnaswamy.^[14] His role has emphasized fostering talent in theoretical areas while integrating complexity theory into emerging technologies.^[16]

Research contributions

Development of the AKS primality test

Neeraj Kayal collaborated with his advisor Manindra Agrawal and fellow student Nitin Saxena at the Indian Institute of Technology Kanpur to develop the AKS primality test, a landmark achievement during Kayal's PhD studies.^[17] The algorithm was first announced in a preprint in August 2002 and formally published in the Annals of Mathematics in 2004.^[17] This work provided the first unconditional, deterministic polynomial-time solution to the primality testing problem.^[17] Prior to the AKS test, primality testing relied on probabilistic methods like the Miller-Rabin algorithm or conditional deterministic approaches assuming the Generalized Riemann Hypothesis (GRH) or using elliptic curves, leaving an open question in computational number theory since the 1970s on whether PRIMES \in \mathsf{P}.^[17] The AKS algorithm resolved this by offering a fully deterministic method independent of unproven conjectures or random choices, marking a theoretical milestone in complexity theory.^[17] It built on earlier ideas like Fermat's Little Theorem but extended them to polynomial rings over finite fields to avoid reliance on analytic number theory.^[17] At its core, the AKS test is a deterministic polynomial-time algorithm that determines whether a given integer n > 1 is prime by verifying a set of polynomial congruences derived from algebraic identities.^[17] The key insight leverages the fact that if n is prime, then for any integer a, the binomial expansion of (X + a)^n simplifies to X^n + a modulo n, and this property extends to the ring of polynomials modulo X^r - 1.^[17] Specifically, the test first checks basic conditions (e.g., n is not divisible by small primes) and then selects an integer r ≤ ⌊log^5 n⌋ such that the multiplicative order of n modulo r exceeds (log_2 n)^2; such an r exists and can be found efficiently.^[17] It then verifies the identity

(X + a)^n \equiv X^n + a \pmod{n, X^r - 1}

for all a from 1 to ⌊√φ(r) log n⌋, where φ is Euler's totient function and gcd(a, n) = 1; if all hold and n passes preliminary checks, n is prime.^[17] These verifications run in polynomial time relative to the input size log n, with the original analysis yielding Õ(log^{15/2} n) time complexity, later heuristically improved to Õ(log^6 n).^[17] The AKS test's impact lies in its proof that primality is in the complexity class \mathsf{P}, resolving a long-standing open problem without probabilistic elements or unproven assumptions.^[17] For this contribution, Agrawal, Kayal, and Saxena received the 2006 Gödel Prize from ACM SIGACT and EATCS for outstanding theoretical computer science papers. They also shared the 2006 Fulkerson Prize from the American Mathematical Society and Mathematical Optimization Society for exceptional work in discrete mathematics.^[18] While theoretically groundbreaking, the algorithm's high-degree polynomial time and large constants render it impractical for testing large numbers compared to faster probabilistic methods.^[17] Neeraj Kayal has made significant contributions to algebraic circuit complexity, focusing on derandomization, lower bounds, and algorithmic advancements in arithmetic circuits post-2002. His work emphasizes efficient testing and reconstruction methods for circuit classes, particularly those with restricted depth, which are central to understanding computational limits in algebraic settings. These efforts build on algebraic techniques to address longstanding problems in complexity theory, including separations between circuit models and their implications for broader computational paradigms.^[19] A key area of Kayal's research involves polynomial identity testing (PIT) for depth-3 arithmetic circuits, denoted as \Sigma\Pi\Sigma circuits, which consist of a sum of products of sums. In collaboration with Nitin Saxena, he developed the first deterministic polynomial-time algorithm for PIT on such circuits, achieving a running time of \tilde{O}(s^{12}) for circuits of size s, where the top fan-in is bounded by the degree. This breakthrough resolved a major open problem by providing a non-blackbox approach that avoids randomization, with applications to verifying circuit identities efficiently. Further extending this, Kayal and Shubhangi Saraf introduced a blackbox PIT algorithm for depth-3 circuits with top fan-in k, running in time (\tilde{d}k)^{O(\log s / \log \log s)} \cdot \text{poly}(s), where d is the degree, enhancing derandomization efforts for multilinear circuits. These results have influenced subsequent derandomization techniques in algebraic complexity.^[20]^[21] Kayal's work also establishes crucial lower bounds for depth-3 circuits, highlighting their limitations. With Ankit Gupta, Pritish Kamath, and Ramprasad Saptharishi, he proved a superpolynomial separation between general depth-3 circuits and those with bounded top fan-in, showing that computing the permanent requires depth-3 circuits of size n^{\Omega(\log n / \log \log n)} under certain restrictions. This "chasm" result demonstrates that restricting the top fan-in to polylogarithmic values exponentially increases circuit size for hard functions, providing evidence for the rigidity of algebraic models. Additionally, in joint work with Chandan Saha, he derived an almost cubic lower bound of n^{3-o(1)} for depth-3 circuits computing specific hard polynomials with small bottom fan-in, advancing proof systems for circuit lower bounds via shifted partial derivatives. These bounds intersect with number theory by analyzing annihilating polynomials and their complexity.^[22]^[23] In the realm of matrix multiplication, Kayal has contributed to lower bounds for iterated matrix multiplication (IMM), a benchmark for algebraic complexity. Collaborating with Prashanth Amireddy, Ankit Garg, Chandan Saha, and others, he established depth-five lower bounds using shifted partials, showing that IMM requires circuit size \exp(\Omega(\sqrt{d \log d})) for d iterations. His earlier work with Saha on depth-4 formulas for IMM yielded multilinear homogeneous lower bounds of n^{\Omega(\log n)}, underscoring the challenges in optimizing matrix powering via algebraic circuits. These results tie into geometric complexity theory (GCT), where Kayal, with Xi Chen and Avi Wigderson, developed the partial derivatives method to prove representation-theoretic lower bounds, such as for iterated matrix multiplication, by analyzing orbit closures and symmetries in variety spaces. This approach reformulates circuit lower bounds as geometric problems, like separating permanents from determinants.^[24]^[25]^[26] More recently, during his tenure at Microsoft Research, Kayal has extended algebraic complexity to interdisciplinary applications, particularly in machine learning. His work on tensor decomposition and unsupervised learning leverages circuit reconstruction techniques; for instance, with Ankit Garg, Nikhil Gupta, and Chandan Saha, he designed algorithms to learn sums of powers of low-degree polynomials in the non-degenerate case, decomposing degree-d polynomials into r terms of powers up to degree k in time polynomial in n, d, r, 1/\epsilon, assuming a non-degeneracy condition on the variety of sums of powers. This geometric intersection—focusing on the variety's structure where polynomials are expressed as \sum_{i=1}^r (\ell_i)^{p_i} with linear forms \ell_i—enables robust recovery from noisy samples, with applications to Gaussian mixture models and subspace learning. In a broader framework with Pritam Chandra, Kunal Mittal, and Tanmay Sinha, he proposed algebraic circuit reconstruction for unsupervised tasks, achieving efficient learning of mixtures via tensor methods that derandomize and generalize classical decompositions. These advancements bridge algebraic lower bounds with AI, evolving from pure theory to practical algorithmic tools.^[27]^[28]

Awards and honors

Major international awards

Neeraj Kayal received the 2006 Gödel Prize, awarded jointly by the Association for Computing Machinery's Special Interest Group on Algorithms and Computation Theory (ACM SIGACT) and the European Association for Theoretical Computer Science (EATCS), for his co-authorship of the paper "PRIMES is in P" that introduced the AKS primality test. This prestigious award recognizes outstanding papers in theoretical computer science and is selected by a committee of international experts based on nominations and impact.^[29] In the same year, Kayal shared the 2006 Fulkerson Prize with Manindra Agrawal and Nitin Saxena, presented by the American Mathematical Society (AMS) and the Mathematical Optimization Society (MOS), again for the AKS primality test paper, highlighting its contributions to discrete mathematics.^[30] The prize honors outstanding research in discrete mathematics with a focus on linear programming and combinatorial optimization, chosen through a rigorous peer-review process by the sponsoring societies.^[18] Kayal was awarded the 2021 Infosys Prize in the Mathematical Sciences category by the Infosys Science Foundation for his foundational work in computational complexity, including algebraic circuit complexity and related algorithmic advancements.^[2] This international award, open to scientists of Indian origin worldwide and under 50 years old, involves nominations from global experts and selection by a jury of renowned mathematicians; it includes a gold medallion, a citation, and a prize of US$100,000.^[31]

National and institutional recognitions

In 2012, Neeraj Kayal received the Young Scientist Award from the Indian National Science Academy (INSA), recognizing his early contributions to computational complexity theory and algorithm design.^[32]^[7] This honor, which includes a medal and research grant, highlights his emerging role in advancing theoretical computer science within India's academic ecosystem.^[32] Kayal was awarded the Shanti Swarup Bhatnagar Prize in Mathematical Sciences for 2022 by the Council of Scientific & Industrial Research (CSIR), with the announcement made in September 2023 after a delay.^[4]^[33] This prestigious national award, named after India's first scientific advisor, acknowledges outstanding research in science and technology, and in Kayal's case, it celebrates his innovations in algebraic algorithms and arithmetic complexity.^[4]^[34] Earlier in his career, in 2003, Kayal earned the Distinguished Alumnus Award from the Indian Institute of Technology Kanpur (IIT Kanpur), his alma mater, where he completed his B.Tech. in 2002 and Ph.D. in 2007.^[7]^[35] This institutional recognition underscores his rapid impact following graduation and ties to his foundational training at one of India's premier engineering institutions.^[7] These awards collectively affirm Kayal's profound influence on the Indian science and technology landscape, bridging academic origins at IIT Kanpur with his ongoing work at Microsoft Research India.^[7]^[35]

References

[1]
[PDF] PRIMES is in P - Microsoft
By Manindra Agrawal, Neeraj Kayal, and Nitin Saxena*. Abstract. We present ... Sudan, Notes on primality test and analysis of AKS,. Private communication ...Missing: original | Show results with:original
[2]
Laureates 2021 - Dr. Neeraj Kayal - Infosys Prize
Dr. Kayal works in the areas of complexity theory, algorithms, and related areas of theoretical computer science. Neeraj Kayal was born in Guwahati, India.
[3]
Neeraj Kayal at Microsoft Research
I am interested in problems related to or at the intersection of Computational Complexity and Algebra, Number Theory and Geometry.
[4]
Dr Neeraj Kayal - Awardee Details: Shanti Swarup Bhatnagar Prize
Dr Kayal has made a significant contributions in developing algorithms in algebra and number theory, as well as novel techniques in arithmetic complexity.
[5]
Mathematical Quest 3: Prime Numbers - Gonit Sora
Jul 9, 2013 · It is also worth noting that Neeraj Kayal was born and brought up in Guwahati. Kayal did his schooling from Don Bosco, Guwahati and then ...Missing: early childhood
[6]
IIT's prime duo achieves celeb status | Mumbai News - Times of India
Sep 2, 2002 · ... Neeraj Kayal got his first taste of celebrity when he went to buy some books. <br />The 22-year-old was warmly welcomed by the shopkeeper ...
[7]
[PDF] PRIMES Is in P: A Breakthrough for "Everyman" - CSE - IIT Kanpur
now, the students Neeraj Kayal and Nitin Saxena. Both were members of the Indian team in the 1997. International Mathematical Olympiad. Studying computer ...
[8]
Dr Neeraj Kayal - IIT Kanpur
Sep 14, 2023 · (BT/PhD/CSE/2002/2007) ... Dr. Neeraj Kayal is an Indian Computer Scientist. He is currently a researcher at Microsoft Research Lab, Bangalore.
[9]
Homegrown at IIT Kanpur - Bhāvanā
MA: My grandparents from my father's side were gone before I was born. So, when I grew up, I had my mother, my father, and my elder brother—just the four of us.
[10]
[PDF] DERANDOMIZING SOME NUMBER-THEORETIC AND ALGEBRAIC ...
Naturally, my warmest thanks are to my advisor. Manindra Agrawal. There is so much that I want to thank him for that I am afraid I will not be able to do a good ...
[11]
Neeraj Kayal - Theory of Computing
Neeraj Kayal graduated from IIT Kanpur in 2006; his advisor was Manindra Agrawal. His thesis focused on questions in algorithmic number theory and algorithmic ...
[12]
[PDF] kayal.pdf
I learnt quite a bit of my mathematics and computer science from him. I am grateful to IIT Kanpur, especially the Department of Computer Science and.<|separator|>
[13]
Postdocs Starting in Academic Year 2017-2018 - DIMACS
Oct 4, 2018 · 2007-2008 (BioMaPS/Rutgers): Debbie Yuster 2007-2008. Postdocs Starting in Academic Year 2006-2007. Neeraj Kayal 2006-2008 (06/07 IAS, 07/08 ...Missing: date | Show results with:date
[14]
[PDF] eric w. allender - Rutgers Computer Science
Jan 27, 2017 · Neeraj Kayal (2007-8) (Now at Microsoft Research, Bangalore). Andrej Bogdanov (2006-7) (Now at Chinese University of Hong Kong). Venkatesh ...
[15]
Podcast: A Random Walk from Complexity Theory to Machine ...
May 29, 2022 · Ravi talks to Neeraj about how he became interested in this area of computer science and his journey till now. Neeraj Kayal: It's just a matter ...Missing: early | Show results with:early
[16]
Microsoft India Research Initiative - Division of EECS, IISc Bangalore
Collaborative research ... Researchers from MSRI: Nishanth Chandran, Amit Deshpande, Ravi Kannan, Neeraj Kayal, Venkat Padmanabhan, Manohar Swaminthan.
[17]
Neeraj Kayal at the Intersection of Mathematics and Computer Science
Oct 10, 2023 · Dr. Neeraj Kayal of Microsoft Research, Bangalore, won the Infosys Prize in Mathematical Sciences in 2021, for his outstanding contributions ...
[18]
Primes is in P - CSE - IIT Kanpur
Missing: original | Show results with:original
[19]
2006 Fulkerson Prize - American Mathematical Society
The 2006 Delbert Ray Fulkerson Prize was pre- sented at the 19th International Symposium on. Mathematical Programming, held July 30 to August.Missing: AKS | Show results with:AKS
[20]
[PDF] POLYNOMIAL IDENTITY TESTING FOR DEPTH 3 CIRCUITS
POLYNOMIAL IDENTITY TESTING FOR. DEPTH 3 CIRCUITS. Neeraj Kayal and Nitin Saxena. Abstract. We study the identity testing problem for depth 3 arithmetic.
[21]
Polynomial Identity Testing for Depth 3 Circuits
We study the identity testing problem for depth 3 arithmetic circuits ( $$\sum\prod\sum$$ circuit). We give the first deterministic polynomial time identit.
[22]
Blackbox Polynomial Identity Testing for Depth 3 Circuits - IEEE Xplore
Blackbox Polynomial Identity Testing for Depth 3 Circuits | IEEE Conference Publication | IEEE Xplore ... Neeraj Kayal; Shubhangi Saraf. All Authors. Sign In or ...
[23]
Arithmetic Circuits: A Chasm at Depth 3 | SIAM Journal on Computing
Arithmetic Circuits: A Chasm at Depth 3. Authors: Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad SaptharishiAuthors Info & Affiliations. https://doi ...Missing: publications | Show results with:publications
[24]
[PDF] An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
[KS15a]. Neeraj Kayal and Chandan Saha. Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin. In Conference on Computational Complexity, ...<|separator|>
[25]
Low-depth arithmetic circuit lower bounds via shifted partials - arXiv
Nov 14, 2022 · Title:Low-depth arithmetic circuit lower bounds via shifted partials. Authors:Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, ...
[26]
Lower Bounds for Depth-4 Formulas Computing Iterated Matrix ...
We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth-4 arithmetic formula computing the ...
[27]
[PDF] Partial Derivatives in Arithmetic Complexity and Beyond Contents
14, 2007. [37] N. Kayal, “The complexity of the annihilating polynomial,” in Proceedings of the 24th Annual IEEE Conference on Computational ...
[28]
Learning sums of powers of low-degree polynomials in the non ...
Apr 15, 2020 · We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an n-variate degree-d polynomial f which ...
[29]
[PDF] Learning Arithmetic Formulas in the Presence of Noise - DROPS
Abstract. We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace ...
[30]
Gödel Prize (together with ACM SIGACT)
The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the ACM SIGACT. This award is presented annually.
[31]
2006 Fulkerson Prize Citation - Mathematical Optimization Society
2006 Fulkerson Prize Citation ... Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160, No. 2, 2004, Pages 781-793.
[32]
Mathematical Sciences - Infosys Prize
Laureates · Manindra Agrawal · Neena Gupta · Bhargav Bhatt · Mahesh Kakde · Neeraj Kayal · Sourav Chatterjee · Siddhartha Mishra · Nalini Anantharaman.
[33]
Awards for Young Indian Scientists Adding Up - Microsoft Research
May 15, 2012 · Neeraj Kayal ... The medal is accompanied by a small research grant from INSA, and Kayal is calculating how to use it most efficiently.
[34]
Centre announces winners of Bhatnagar Prize after a year's delay
Sep 11, 2023 · The winners of the 2022 Shanti Swarup Bhatnagar Prize awarded for ... Neeraj Kayal, Microsoft Research Lab India (Mathematical Science); ...<|control11|><|separator|>
[35]
Shanti Swarup Bhatnagar Prize - Ministry of Education
Sep 20, 2023 · Dr Neeraj Kayal. Department of Mathematics and Computing Microsoft Research Lab India Bengaluru 560 001. neeraka[at]microsoft[dot]com. Medical ...<|control11|><|separator|>
[36]
Designing Efficient Algorithms for Algebraic Circuits
Apr 19, 2024 · Dr Neeraj Kayal has won the Shanti Swarup Bhatnagar Prize and Infosys Prize for Computational Complexity. Share. Facebook Twitter LinkedIn ...