Derandomization that is rarely wrong from short advice
that is typically good
Webpage for a paper by Oded Goldreich and Avi Wigderson
Abstract
For every $\eps>0$,
we present a log-space deterministic algorithm
that correctly decides undirected graph connectivity
on all but at most $2^{n^\eps}$ of the $n$-vertex graphs.
The same holds for every problem in Symmetric Log-space (i.e., $SL$).
Using a plausible complexity assumption
(i.e., that $P$ cannot be approximated by $size(p)^SAT$,
for every polynomial $p$)
we show that, for every $\eps>0$, each problem in $BPP$ has
a polynomial-time deterministic algorithm that errs
on at most $2^{n^\eps}$ of the $n$-bit long inputs.
(The complexity assumption that we use is not known to imply $BPP=P$.)
Both results are obtained as special cases of a general methodology
that explores which probabilistic algorithms can be derandomized by
generating their coin tosses deterministically from the input itself.
We show that this is possible (for all but extremely few inputs) for
algorithms which take advice (in the usual Karp-Lipton sense), in
which the advice string is short, and most choices of the advice
string are good for the algorithm.
To get the applications above and others,
we show that algorithms with short and typically-good advice
strings do exist, unconditionally for $SL$,
and under reasonable assumptions for $BPP$ and $AM$.
Material available on-line
Errarata (2002)
An intermediate version, which unfortunately appeared also
in the RANDOM'02 proceedings claimed analogous results
for primality testing. These claims were retracted
a few weaks after they were made, but the publisher
has mixed up the two versions.
(The error was due to fact that the text gave an incorrect account
of the randomized primality tester. This account was
based on our bad memory and it was quite careless of us
not to have double-checked it before writing. In any case,
we detected the error later and corrected the write-up,
but the publisher used the old version.)
Errarata (2017)
Thm3 and Thm9 are ill-stated,
since they lack a restriction on $\ell$;
the original intention was to state these
results only for $\ell(n)=n^{\Omega(1)}$.
We seize the opportunity to augment FN6 by pointing out that
the weak design can be constructed pseudodeterministically;
specifically, sets that are selected in a pairwise independent
manner will do, and the probability that there exists a pair
of sets with too large intersection can be charged to the error
parameter of the extractor.
Back to
either Oded Goldreich's homepage.
or general list of papers.