zbMATH — the first resource for mathematics

Derandomization that is rarely wrong from short advice that is typically good. (English) Zbl 1028.68225
Rolim, José D. P. (ed.) et al., Randomization and approximation techniques in computer science. 6th international workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2483, 209-223 (2002).
Summary: For every \(\epsilon >0\), we present a deterministic log-space algorithm that correctly decides undirected graph connectivity on all but at most \(2^{n^\epsilon}\) of the \(n\)-vertex graphs. The same holds for every problem in Symmetric Log-space (i.e., \({\mathcal {SL}}\)).
Using a plausible complexity assumption (i.e., that \({\mathcal P}\) cannot be approximated by SIZE\((p)^{\text{SAT}} \), for every polynomial \(p\)) we show that, for every \(\epsilon >0\), each problem in \({\mathcal {BPP}}\) has a deterministic polynomial-time algorithm that errs on at most \(2^{n^\epsilon}\) of the \(n\)-bit long inputs. (The complexity assumption that we use is not known to imply \({\mathcal {BPP = P}}\).)
All 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 \({\mathcal {SL}}\), and under reasonable assumptions for \({\mathcal {BPP}}\) and \({\mathcal {AM}} \).
For the entire collection see [Zbl 1001.00041].

68W20 Randomized algorithms
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: Link