Title: SL=L (well, almost...) and Other Rarely-wrong Derandomizations
Speaker: Avi Wigderson, IAS Princeton, and Hebrew University, Jerusalem
Date: November 17, 2003 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
For every e>0, we present a log-space deterministic algorithm that correctly decides undirected graph connectivity on all but at most exp(n^e) of all n-vertex graphs. The same holds for every problem in Symmetric Log-space (SL). Using a plausible complexity assumption (which is not know to imply BPP=P) we show that, for every e>0, each problem in BPP has a polynomial-time deterministic algorithm that errs on at most exp(n^e) of all n-bit long inputs. The same holds if we replace BPP by MA and deterministic by nondeterministic algorithms. The results are obtained by exploring which probabilistic algorithms can be derandomized (in the sense above) by generating their coin tosses deterministically from the input itself.