### 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

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.