Derandomization that is rarely wrong from short advice that is typically good

Webpage for a paper by Oded Goldreich and Avi Wigderson


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.