Friday, April 01, 2005

Another Breakthrough!

Speaking of space complexity, Adam Kalai, Adam Klivans and Rocco Servedio have extended Reingold's result to show that every language in randomized logarithmic space has a deterministic log-space simulation, i.e., RL = L. Cool.

You can find a copy of their paper here.

5 comments:

  1. Should there be a qualifier here that it's April 1st?

    ReplyDelete
  2. I've shown that every problem in EXPSPACE can be solved by spitting on the sidewalk and analyzing the bubbles in the resultant globule.

    ReplyDelete
  3. What happend ? NP=P is not good enough for being a prank anymore ?

    ReplyDelete
  4. The link doesn't work!

    ReplyDelete