PRIMES is in P

George Heineman

CS Dept., WPI

Friday September 15, 2006
11:00 a.m. - 12:00 p.m.
Fuller Labs 320

In August of 2002, the team of Manindra Agrawal, Neeraj Kayal,
and Nitin Saxena electrified the Mathematics and Computer
Science communities with their publication simply entitled,
”PRIMES is in P”
http://annals.math.princeton.edu/issues/2004/Sept2004/Agrawal.pdf
Algorithms are considered to be efficient if they can be proven
to belong to the polynomial class P. For quite some time

(at least 2,400 years) the question of determining whether a given
integer N is prime has eluded attempts to determine whether it
can be solved by an efficient algorithm.
All previously known polynomial time primality tests were based
on probabilistic methods or they relied on an unproven
assumption, known as the generalized Riemann Hypothesis. The
result obtained by Agrawal, Kayal, and Saxena can be seen as a
crowning achievement of a long algorithmic and mathematical
quest. A remarkable aspect of the article is that the final
exposition itself turns out to be rather simple; while there are
are some nifty tricks and techniques used, the mechanics of the
proof are still accessible to the community at large.
______

Prof. Heineman has a PhD from Columbia University. He is the author of “Component Based Software Engineering: Putting the Pieces Together, Addison-Wesley, 2001. His research interests include Software Engineering, Object-oriented Design, and Feature-based Software Composition. He fills his days with programming, time with his family and young son, and unsolved mathematical conjectures.

Host: Host: Michael Gennert

Refreshments will be served.