This work is licensed under a
Creative Commons License.
|
Monday, December 13, 2004
Favorite Theorems: Derandomizing Space
Posted by Lance
November EditionWe started this list of favorite theorems with derandomization of time classes. Now we end the list by looking at derandomizing space-bounded classes.
Over the last fifteen years we have seen several exciting results on removing randomness from space. Unlike time they require no hardness assumptions but until very recently didn't achieve full derandomization.
The techniques of Savitch's Theorem give us that randomized logarithmic space sits in deterministic log2 space. We will focus on results that reduce the space needed to simulate randomized algorithms and the space for the most well-known randomized space algorithm, undirected s-t-connectivity.
Aleliunas, Karp, Lipton, Lovász and Rackoff showed that one can solve s-t connectivity in randomized logarithmic space by taking a random walk on the graph. Nisan, Szemeredi and Wigderson give a log3/2 algorithm for s-t connectivity. Saks and Zhou give the same bound for every problem in randomized log space.
BPHSPACE⊆DPSACE(S3/2) by Michael Saks and Shiyu Zhou Saks and Zhou's result remains the best known bound for randomized logarithmic space but we can do better for s-t connectivity. Armoni, Ta-Shma, Wigderson and Zhou improved the s-t connectivity bound to log4/3 space. And just a few weeks ago we had Reingold's result putting s-t connectivity in the optimal logarithmic space, currently a front runner for the next favorite theorems list in 2014.
11:51 AM #
-
Another recommended version of the Saks and Zhou article is their original IEEE FOCS 1995 extended abstract.
Although this does not have the proof of the direct application of the Nisan generator (which is completely proven in the JCSS version), it is very polished and has all the other content without the egregious typesetting errors of the JCSS version.
Having both copies in hand would be best.
Paul Beame
Links to this post:
Weblog Home
Archives
