Computational Complexity

Friday, August 23, 2002

 

Posted by Lance

This has been an exciting summer for computational complexity.

• 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!

Food for thought from Joe Kilian: Primality, until now, has always been the key example of a problem that we knew how to solve quickly with a probabilistic algorithm but not without using randomness. If the new primality algorithm had been discovered in the 70's would randomized complexity still have developed as well as it did?

8:03 PM # 0 comments

Comment Feeds: This Post All