- Complexity Theorist Manindra Agrawal and his students Nitin Saxena and Neeraj Kayal have given the first provably efficient algorithm for primality. This is a breakthrough result, exciting not only as an answer to a long-standing and important problem, but also in the beauty and simplicity of the solution.
- The computational complexity conference held in Montreal broke all records with a 140 participants. I can't wait for next year's conference in Aarhus, Denmark. Check out the new website for the conference, computationalcomplexity.org.
- Kudos to Madhu Sudan, winner of the Nevanlinna Prize for his work on probabilistically checkable proofs and error-correcting codes. This prize is given with the Fields medal every four years for work in "information science". Congrats Madhu!
Friday, August 23, 2002
This has been an exciting summer for computational complexity.