October 20, 2016

Special Lecture

May 23, 2003 -- 3:30 pm

Manindra Agrawal
A Polynomial-time Algorithm for Primality Testing

Audio and Slides of Talk

Manindra Agrawal was born in May 1966, and since 2001 he has been a full professor at the Indian Institute of Technology in Kanpur, India. He has been active over the past ten years in the field of decision theory, complexity, and the relation between the geometry of sets and their information content. For some years he has been interested in finding a polynomial time algorithm to test whether a given number is prime. Although random algorithms can solve this problem with high certainty in polynomial time, it remained a long-standing challenge to find a method that works in every case.

To the great surprise of the experts, Agrawal solved this problem in August 2002, working together with two undergraduate students: Neeraj Kayal and Nitin Saxena. Their proof establishes the correctness of a conjecture made in 1999 by Agrawal and Biswas.