TRDDC Distinguished Lecture
Dr  M A N I N D R A  A G R A W A L

Dr Manindra Agrawal delivered the first TRDDC Distingushed Lecture on 17^th January 2003. He presented his path-breaking PRIMES Is in P paper to an audience of more than 100 people, including many invitees from various academic institutes, research labs, and industries in and around Pune.

Dr Agrawal is a professor in the Department of Computer Science and Engineering at Indian Institute of Technology, Kanpur. Recently, he won instantaneous world fame after announcing his result about polynomial time primality testing. Starting from ancient Chinese and Greek mathematicians, many people had worked on this problem of finding an efficient algorithm for testing if a number is a prime. 

Numerous ingenious algorithms were designed: some deterministic, but conditionally polynomial-time, and others polynomial-time, but probabilistic. Yet the ultimate goal of this line of research was to obtain an unconditional deterministic polynomial-time algorithm for primality testing, and despite the impressive progress made in primality testing, this goal remained elusive for over two thousand years. Quite a few even doubted its feasibility.

Remarkably, working only with his undergraduate students, Neeraj Kayal and Nitin Saxena, Dr. Agrawal achieved the final breakthrough. In their paper—consisting of just 9 pages—titled ‘PRIMES is in P’, the authors presented the first unconditional, deterministic, polynomial-time algorithm for testing if a number n is prime.