Fact-checked by Grok 2 weeks ago

Manindra Agrawal

Manindra Agrawal (born 20 May 1966) is an best known for co-developing the , the first deterministic polynomial-time algorithm to determine whether a given number is prime, thereby proving that the problem of primality testing belongs to the . A professor in the Department of at the Institute of Technology Kanpur (), he has held numerous administrative roles there, including director since April 2024, and his research focuses on , , , and pandemic modeling. Agrawal earned his B.Tech. in 1986 and Ph.D. in 1991, both in from . After his doctorate, he worked as a fellow at the SPIC Science Foundation in and as a Humboldt Fellow at the in before joining the IIT Kanpur faculty in 1996. Over the years, he has served as head of the Department of (2006–2010), Dean of Resource Planning and Generation (2011–2012), Dean of Faculty Affairs (2013–2015), Deputy Director (2017–2019), and Project Director of C3iHub (2020–2024). In 2002, Agrawal, along with his then-undergraduate students and Nitin Saxena, published the seminal paper "PRIMES is in P", which introduced the AKS algorithm—a breakthrough that resolved a long-standing in by providing an efficient, unconditional method for primality testing without relying on unproven hypotheses like the Generalized . The algorithm's significance lies in its placement of primality in P, advancing and having practical implications for and applications. Beyond AKS, Agrawal has contributed to areas such as efficient algorithms for the "P vs NP" question and complexity of computation. Agrawal's achievements have been recognized with numerous prestigious awards, including the in 2002, Prize in 2003, ICTP Prize in 2003, in 2006, in 2006, in 2008, and in 2013. He is a fellow of the (USA), , the Indian National Science Academy, the Indian Academy of Sciences, and the Indian National Academy of Engineering.

Early life and education

Early life

Manindra Agrawal was born on 20 May 1966 in , , . He grew up in a of four, consisting of his parents and an elder brother, in a modest academic household; his grandparents had passed away before his birth. Both parents were educators—his father taught , and his mother worked in education—which fostered an environment conducive to learning in the culturally rich city of Allahabad, renowned for its academic institutions like Allahabad University. Details about his family remain limited in public records, but Agrawal has described his upbringing as middle-class, where studies came naturally to him without excessive effort, often beginning preparations close to exam times. Agrawal's early exposure to mathematics and science occurred through local schooling, including attendance at Government Inter College in Allahabad for his 11th and 12th grades, where he developed a particular affinity for due to its precision and problem-solving nature, finding subjects like comparatively less engaging. He enjoyed tackling creative problems from correspondence courses such as Agarwal Classes and light reading materials like Champak magazine and books, though he avoided deeper philosophical texts. This interest in analytical challenges, encouraged by his brother's suggestion, propelled him toward competitive examinations like the (JEE), which he approached with minimal prior preparation but cleared with a high rank, paving the way for his pursuit of higher education at .

Education

Manindra Agrawal enrolled at the in 1982 as part of the B.Tech. batch in . His undergraduate studies, which spanned from 1982 to 1986, provided him with a strong foundation in computing, shifting his initial interest from programming to theoretical aspects of algorithms and . He completed his B.Tech. degree in in 1986. Following his , Agrawal pursued a Ph.D. in at the same institution, completing it in 1991. His doctoral research, supervised by Somenath , focused on topics in . The thesis, titled Towards a Characterization of NP-Complete Sets, explored properties of NP-complete problems. During his Ph.D., Agrawal engaged in research projects centered on , including the study and development of new properties for NP-complete sets. These efforts under Biswas's guidance laid essential groundwork for his subsequent contributions to algorithms and .

Career

Early career

Following his Ph.D. in from in 1991, Manindra Agrawal served as at from January 1992 to February 1993. He then began his professional career with a fellowship at the School of Mathematics, SPIC Science Foundation (now ) in , , from March 1993 to June 1995. During this period, he focused on foundational research in algebra and computation, exploring connections between algebraic structures and computational models that laid groundwork for his later contributions to . This role provided him with an environment to develop early ideas in , emphasizing rigorous mathematical approaches to algorithmic problems. In 1995, Agrawal transitioned to an international position as a Humboldt at the in , where he served from July 1995 to July 1996. This prestigious fellowship supported his research in , particularly in and problems, while fostering collaborations with European researchers in the field. The experience abroad broadened his perspective on global advancements in computational theory and enhanced his expertise through interactions with leading scholars. Agrawal's initial publications during this early career phase centered on , including works on polynomial of complete sets, the conjecture for weak reducibilities, and decision versus search problems for . These contributions, published in journals such as the Journal of Computer and Systems Sciences and Information and Computation between 1993 and 1996, established his reputation in analyzing the structural properties of computational problems and paved the way for his subsequent developments in number-theoretic algorithms.

Positions at IIT Kanpur

Manindra Agrawal joined the faculty of the Indian Institute of Technology Kanpur (IIT Kanpur) in 1996 as an Assistant Professor in the Department of Computer Science and Engineering. Over the subsequent years, he advanced through the academic ranks, becoming Associate Professor in 1999 and attaining the position of full Professor in 2001. In 2003, he was appointed to the N. Rama Rao Chair in Computer Science, a prestigious endowed position recognizing his contributions to the field. Throughout his tenure at IIT Kanpur, Agrawal has been actively involved in teaching, delivering courses that cover core areas of . Notable among these are CS640 on , which explores the foundational limits of efficient computation, and CS681 on Computational Algebra and , focusing on algebraic structures and their algorithmic applications in number-theoretic problems. These courses have provided students with rigorous training in advanced topics, emphasizing both theoretical insights and practical computational techniques. Agrawal has also played a significant role in mentoring graduate students, supervising Ph.D. candidates who have gone on to make notable contributions in computational theory. He mentored students including Neeraj Kayal and Nitin Saxena, who as undergraduates collaborated with him on the AKS primality test and later pursued Ph.D.s under his supervision. This mentorship underscores his commitment to fostering the next generation of researchers in the department. During the academic year 2003–2004, Agrawal served as a visiting scholar at the Institute for Advanced Study in , while retaining his primary affiliation with . This sabbatical allowed him to engage with leading international scholars, further enriching his academic perspective upon his return to the institute.

Leadership roles

Manindra Agrawal served as Head of the Department of from 2006 to 2010, Dean of Resource Planning and Generation from 2011 to 2012, and Dean of Faculty Affairs from 2013 to 2015. He served as of the Indian Institute of Technology (IIT ) from 2017 to 2019, where he played a key role in overseeing academic and research initiatives at the institute. In this capacity, he contributed to strategic planning and administrative functions, supporting the director in managing institute operations and fostering growth in educational and research programs. From 2020 to 2024, he was Project Director of C3iHub, a cybersecurity technology innovation hub at IIT Kanpur. On 19 April 2024, Agrawal was appointed Director of IIT Kanpur, succeeding Prof. Indranil Manna, with a focus on enhancing the institute's research output, infrastructure development, and global collaborations. As Director, he has prioritized initiatives such as forging international partnerships for shared research and development expertise, including memoranda of understanding with institutions like Vietnam National University and IIIT Una to advance academic excellence. He has also overseen infrastructure upgrades, exemplified by the inauguration of the Faculty Building Annex in June 2025 to improve campus facilities. Additionally, Agrawal has driven collaborations with state governments, such as with Uttar Pradesh, to position IIT Kanpur as a hub for deep tech and drone technologies. Throughout his long-term faculty tenure at , Agrawal has been involved in policy-making for and the expansion of computational programs. His leadership in these areas has contributed to strengthening 's offerings in and related interdisciplinary programs.

Research contributions

AKS primality test

The is a landmark for verifying the primality of a positive n, developed in 2002 by Manindra Agrawal along with his students and Nitin Saxena (then undergraduates) at the Indian Institute of Technology Kanpur. The trio announced their breakthrough that August, demonstrating that primality testing can be performed in polynomial time without relying on randomization or unproven hypotheses, and formally published the result as "PRIMES is in P" in the Annals of Mathematics in 2004. This work established that the of determining whether a number is prime belongs to the P, resolving a major open question in . The algorithm addressed a challenge persisting since the , when probabilistic methods like the Miller-Rabin test (introduced in 1976) offered efficient but non-deterministic primality checks, and deterministic approaches, such as Miller's 1975 test, depended on the Extended (ERH). Earlier deterministic algorithms, like that of Adleman, Pomerance, and Rumely from 1983, achieved subexponential time but fell short of polynomial bounds. The AKS test provided the first unconditional, deterministic polynomial-time solution, eliminating any need for assumptions like the Generalized (GRH) required in prior conditional results, such as Pratt's 1975 proof of PRIMES in P under GRH. This 25-year gap since the initial probabilistic advances marked a profound advancement in . Technically, the AKS builds on by extending it to polynomial identities over finite rings, utilizing properties of cyclotomic polynomials and in \mathbb{Z}/n\mathbb{Z}. The procedure begins by ruling out if n is a perfect power or has small prime factors up to a parameter r, where r is the smallest prime such that the multiplicative order of n r exceeds (\log n)^2. It then verifies a series of congruences: for values of a from 1 to roughly \sqrt{\phi(r)} \log n, check if (x + a)^n \equiv x^n + a \pmod{x^r - 1, n}, where \phi is . If all hold and no prior checks indicate compositeness, n is prime. The original analysis yields a of \tilde{O}(\log^{10.5} n), with a heuristic assumption ( primes) reducing it to \tilde{O}(\log^6 n); subsequent refinements by Lenstra and Pomerance in confirmed the \tilde{O}(\log^6 n) bound . The AKS test's impact reverberates through and complexity, offering an algebraic framework that has inspired extensions to identity testing and factoring problems, while solidifying primality's place in deterministic polynomial-time computation. In , where reliable prime generation underpins systems like , it provides a theoretical guarantee of efficiency, though practical implementations favor faster probabilistic tests due to AKS's higher constants. The discovery garnered widespread recognition, including prestigious awards for its authors, and continues to influence research in algebraic algorithms for number-theoretic problems.

Other work in complexity and number theory

Agrawal has advanced the field of through influential results on lower bounds for arithmetic . A landmark contribution is his 2008 paper with V. Vinay, which established a significant separation between depth-3 and depth-4 arithmetic circuits by proving that the permanent polynomial requires circuits of superpolynomial size at depth four, highlighting a "chasm" in . This work has inspired subsequent research on depth-restricted models and their limitations. Additionally, in a 2005 paper, Agrawal introduced techniques using pseudo-random generators to derive unconditional lower bounds for certain circuit classes, aiding derandomization efforts by linking randomized complexity to deterministic ones. His research bridges with , employing tools like the criterion to construct hitting sets and prove lower bounds. In the 2012 collaboration with C. Saha and R. Saptharishi, they showed that Jacobian-based constructions yield efficient hitting sets for read-once oblivious algebraic branching programs and depth-3 circuits with bounded transcendence degree, while also establishing exponential lower bounds for depth-D occur-k formulas. These results leverage geometric properties of varieties to address long-standing challenges in algebraic , influencing both theoretical bounds and practical identity testing algorithms. Further, Agrawal's 2018 work with N. Limaye, P. Malurkar, and S. Srinivasan on variables in algebraic circuits demonstrated superpolynomial lower bounds for circuits computing hard polynomials, connecting to broader themes in proof and algebraic proof systems. In , Agrawal has extended his explorations beyond primality to factoring algorithms and lattice-based methods. His 2007 lecture series on rings and integer lattices in outlined applications of techniques, such as , to and cryptographic problems, emphasizing their role in solving Diophantine approximations and subgroup membership in finite rings. This connects to derandomization in number-theoretic contexts, where lattices help isolate short vectors for efficient deterministic factoring under certain assumptions. Complementing this, his 2005 paper with N. on automorphisms of finite rings provided complexity characterizations with implications for cryptographic protocols, including hardness results for problems like over rings. Agrawal's broader impact includes over 100 publications in and , amassing more than 4,600 citations and an of 27 as of 2025. In recent years, he has applied computational methods to real-world challenges, notably developing the model for dynamics. Introduced in 2021 with M. Kanitkar, D. Phillip, T. Roychowdhury, and M. Vidyasagar, incorporates susceptible, undetected, tested, recovered, and asymptomatic compartments to simulate transmission, enabling data-driven estimates of underreported cases and intervention effects in . This model, refined in subsequent works, has informed public health policy by quantifying mortality undercounting and thresholds.

Awards and honors

Major scientific prizes

In 2002, Manindra Agrawal received the from the for his groundbreaking work on primality testing, specifically for developing, in collaboration with undergraduate students and Nitin , a deterministic polynomial-time algorithm that placed the problem in the complexity class . The 2006 , 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), was given to Agrawal, Kayal, and Saxena for their paper "PRIMES is in ," published in the , which provided the first unconditional deterministic polynomial-time , resolving a longstanding without reliance on unproven hypotheses or randomization. That same year, Agrawal, along with Kayal and Saxena, was awarded the by the (AMS) and the Mathematical Programming Society (MPS) for their contributions to through the , which elegantly combined algebraic and number-theoretic techniques to achieve polynomial-time efficiency. In 2008, Agrawal was the inaugural recipient of the in the Mathematical Sciences from the Infosys Science Foundation, recognized for his outstanding contributions to , particularly the resolution of the primality testing problem and its implications for algorithmic efficiency in computation and algebra.

Fellowships and national honors

Manindra Agrawal received the , India's fourth-highest civilian award, in 2013 for his distinguished contributions to science and engineering. This national honor recognizes his pioneering work in , particularly the development of the . Agrawal has been elected as a fellow to all three major Indian science academies, underscoring his profound impact on . He became a Fellow of the Indian National Science Academy (INSA) in 2008, specializing in the . In 2004, he was elected to the fellowship of the under the Engineering and Technology section. Additionally, he is a Fellow of The National Academy of Sciences, India (NASI), reflecting his sustained contributions to the growth of scientific research in the country. He is also a Fellow of the Indian National Academy of Engineering (INAE). On the international stage, Agrawal was elected as a member of (TWAS) in 2012, acknowledging his role in advancing science in developing countries. In 2011, he received the Humboldt Research Award from the for his outstanding research achievements and sustained international impact. He was elected Foreign Associate of the (USA) in 2015. Among his early national recognitions, Agrawal was awarded the Prize in Mathematical Sciences in 2003 by the Council of Scientific and Industrial Research (CSIR) for his innovative algorithms in and . That same year, he received the ICTP Prize in the Structure and Randomness in Computability and Mathematics category from the (ICTP), highlighting his foundational contributions to primality testing.

References

  1. [1]
    Laureates 2008 - Prof. Manindra Agrawal - Infosys Prize
    Born on May 20, 1966 in Allahabad, Prof. Manindra Agrawal received his B. Tech and Ph. D in Computer Science and Engineering from the Indian Institute of ...
  2. [2]
    Prof Manindra Agrawal - IIT Kanpur
    He received his BTech and PhD in Computer Science and Engineering from IIT Kanpur in 1986 and 1991, respectively. He later worked as a fellow at the School of ...<|control11|><|separator|>
  3. [3]
    Manindra Agrawal - Google Sites
    I work in Complexity Theory and Computational Number Theory. Besides, I have an interest in Cryptography and Pandemic Modeling.Students · Publications · Talks · TeachingMissing: biography | Show results with:biography
  4. [4]
    PRIMES is in P - Annals of Mathematics - Princeton University
    PRIMES is in P. Pages 781-793 from Volume 160 (2004), Issue 2 by Manindra Agrawal, Neeraj Kayal, Nitin Saxena. Abstract. We present an unconditional ...
  5. [5]
    Home Page of Manindra Agarwal - CSE - IIT Kanpur
    Distinguished Alumnus award by Indian Institute of Technology, Kanpur, 2003. The Clay Research Award, 2002. The Young Scientist Award by the UP Council for ...Missing: list | Show results with:list
  6. [6]
    Manindra Agrawal – NAS - National Academy of Sciences
    Agrawal was born in Allahabad, UP (India) in 1966. He did his BTech and PhD, both in computer science, from Indian Institute of Technology Kanpur in 1986 and ...
  7. [7]
    Prof Manindra Agrawal - IIT Kanpur
    Jul 4, 2021 · Prof. Manindra Agrawal was born on 20th May 1966 at Allahabad, Uttar Pradesh. He received his B.Tech. and Ph.D. in Computer Science and Engineering from IIT ...
  8. [8]
    Homegrown at IIT Kanpur - Bhāvanā
    We would like to know a bit about your upbringing and family, and how it influenced your trajectory. Young Manindra Agrawal in 1967. Manindra Agrawal. MA: My ...Missing: background | Show results with:background
  9. [9]
    Manindra Agrawal - Computational Complexity Theory - IIT Kanpur
    Education · PhD (Computer Science), IIT Kanpur, 1991 . Thesis Title: Towards a Characterization of NP-Complete Sets Supervisor: Somenath Biswas · B.Tech (Computer ...
  10. [10]
    [PDF] Curriculam Vitae - IIT Kanpur
    Curriculam Vitae. MANINDRA AGRAWAL, N. Rama Rao Chair Professor. Department of Computer Science and Engineering. Indian Institute of Technology. Kanpur 208016 ...
  11. [11]
    Prof. Dr. Manindra Agrawal - Profile - Alexander von Humboldt-Stiftung
    Professor Manindra Agrawal is an international authority in theoretical computer science. In 2002, Professor Agrawal and his students Kayal and Saxena ...
  12. [12]
    Home Page of Manindra Agarwal - CSE - IIT Kanpur
    Teaching. Courses taught: CS681 (Computational Algebra and Number Theory). CS641 (Modern Cryptology). ESO211 (Data Structure and Algorithms). CS201 (Discrete ...
  13. [13]
    Acid Test for Primes | Science | AAAS
    Manindra Agrawal, a professor of computer science, and two students, Neeraj Kayal and Nitin Saxena, announced their result early this month, e-mailing ...
  14. [14]
    Organizers - Pan IIT Meeting |
    Manindra Agrawal is an eminent Professor ... He served as the Deputy Director of IIT Kanpur (2017 – 2021) and joined as the Director of IIT Kanpur in 2024.
  15. [15]
    Prof. Manindra Agrawal Appointed IIT Kanpur Director
    Prof. Manindra Agrawal has been appointed as the director of premier technological institute Indian Institute of Technology (IIT) Kanpur. Currently Professor S ...
  16. [16]
    Six Directors Appointed, Including IIT-Kanpur's Manindra Agrawal
    Apr 19, 2024 · Deputy director of IIT-Kanpur, Manindra Agrawal, has been appointed as director of Kanpur. He is a professor at the department of computer ...
  17. [17]
    Forge Strategic Partnership for Academic and Research Excellence
    Jun 20, 2025 · Prof. Manindra Agrawal, Director of IIT Kanpur, stated, "This collaboration with IIIT Una is another step towards fostering a culture of ...
  18. [18]
    iitkanpur signed a Memorandum of Understanding (MoU ... - Facebook
    Sep 19, 2025 · Leaders' Take: "International academic collaboration to tackle pressing challenges through shared R&D expertise," says Prof. Manindra Agrawal, ...
  19. [19]
    Professor Manindra Agrawal: IIT-K Expert Calls for Reduced ...
    May 5, 2025 · IIT-Kanpur is collaborating with the UP government to boost development, focusing on becoming a deep tech and drone hub, according to ...
  20. [20]
    Manindra Agrawal – Mentor - IKAN
    Manindra has been Dean of Faculty Affairs, Dean of Resources and Alumni and Head, Department of Computer Science and Engineering at IIT Kanpur. He is the winner ...Missing: policy making
  21. [21]
    [PDF] PRIMES is in P - Microsoft
    PRIMES is in P. By Manindra Agrawal, Neeraj Kayal, and Nitin Saxena*. Abstract. We present an unconditional deterministic polynomial-time algorithm that.
  22. [22]
    The AKS primality test | What's new - Terry Tao - WordPress.com
    Aug 11, 2009 · The Agrawal-Kayal-Saxena (AKS) primality test, discovered in 2002, is the first provably deterministic algorithm to determine the primality of a given number.
  23. [23]
    Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k ...
    Nov 2, 2011 · Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. Authors:Manindra ...
  24. [24]
    Bootstrapping variables in algebraic circuits - PNAS
    This contribution is part of the special series of Inaugural Articles by members of the National Academy of Sciences elected in 2015. Contributed by Manindra ...
  25. [25]
    [PS] Rings and Integer Lattices in Computer Science Manindra Agrawal
    The most important classical factoring algorithms are elliptic curve factoring, the quadratic sieve, and the number field. sieve. The fastest classical ...
  26. [26]
  27. [27]
    [2101.09158] SUTRA: A Novel Approach to Modelling Pandemics ...
    Jan 22, 2021 · SUTRA: A Novel Approach to Modelling Pandemics with Applications to COVID-19. Authors:Manindra Agrawal, Madhuri Kanitkar, Deepu Phillip, Tanima ...Missing: publications cryptography
  28. [28]
    Modelling the first wave of COVID-19 in India - Research journals
    We focus on the first wave of the Indian pandemic, across the interval Jan 30, 2020 to Feb 15, 2021. We estimate that deaths were under-counted by a factor ...Missing: Manindra cryptography
  29. [29]
    2002 Archives - Clay Mathematics Institute
    The 2002 Clay Research Award was made to Manindra Agrawal for his work on primality testing; for finding, jointly with two undergraduate students, an algorithm ...
  30. [30]
    2006 Godel Prize
    ### Summary of 2006 Gödel Prize Announcement
  31. [31]
    2006 Fulkerson Prize Citation - Mathematical Optimization Society
    MPS Prizes. 2006 Fulkerson Prize Citation. Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160, No. 2, 2004, Pages ...Missing: AMS | Show results with:AMS
  32. [32]
    P08-1453 - INSA :: Fellow Detail
    Oct 31, 2025 · Name : Professor Manindra Agrawal (Professor Manindra Agrawal), Gender : M · Qualification : Phd ; Specialization : Theory of Computation ...
  33. [33]
    Prof. Manindra Agrawal - Fellows - Indian Academy of Sciences
    Prof. Manindra Agrawal. Ph.D. (IIT, Kanpur), FNAE, FNA, FNASc, FTWAS. Elected into the fellowship in 2004 under the Engineering and Technology section.
  34. [34]
    AGRAWAL, Manindra - The National Academy of Sciences, India
    List of NASI Fellows Elected in 2025 · Proforma for the Fellowship- NASI ... AGRAWAL, Manindra. AGRAWAL, Manindra Theory of Computation. Post navigation.<|separator|>
  35. [35]
    Agrawal, Manindra - TWAS
    May 2, 2025 · Agrawal is Professor in Computer Science department at IIT Kanpur. He obtained his PhD in 1991 from the same department, spent a few years in Chennai ...
  36. [36]
    Manindra Agrawal - Awardee Details: Shanti Swarup Bhatnagar Prize
    Brief Profile of the Awardee · Dr Manindra Agrawal. Award Year: 2003; Discipline: Mathematical Sciences; Date of Birth: 20/05/1966; Specialization: ...
  37. [37]
    ICTP Prize Winner 2003
    The 2003 ICTP Prize has been awarded to Manindra Agrawal from the Indian Institute of Technology, Kanpur, India (presently, Member at the School of ...