We 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.
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.