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,
  • 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?


  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