DIMACS Theoretical Computer Science Seminar

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


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.