Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Friday, April 01, 2005
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.