Friday, August 23, 2002

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?

2 comments:

  1. Hi mr... fortnow i'm a student from mexico and i can't find some good articles of computational complexity, i'm not searching for something beyond of my understanding, but can you sugest me some books? or articles, i mean basic ones, i'm on my freshman year studying software technology engineering, sorry if i have grammar mistakes and greetings :D

    ReplyDelete