Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-049 | 10th July 1998 00:00

Random Walks, Conditional Hitting Sets and Partial Derandomization


Authors: Dimitris Fotakis, Paul Spirakis
Publication: 30th August 1998 09:09
Downloads: 2120


In this work we use random walks on expanders in order to
relax the properties of hitting sets required for partially
derandomizing one-side error algorithms. Building on a well-known
probability amplification technique [AKS87,CW89,IZ89], we use
random walks on expander graphs of subexponential (in the
random bit complexity) size so as to avoid particular sets of
"misleading" strings, while reducing the random bit complexity
of the algorithm.

Then, we introduce the idea of conditional hitting sets in order to
avoid the remaining "misleading" strings. In particular, given a set
C, a $C_1 \subseteq C$, and an $s \not\in C_1$, we suggest to exploit
s for constructing a set that avoids C. Furthermore, we show how to
combine random walks on expanders of subexponential size with
conditional hitting sets so as to reduce the random bit complexity
of any one-side error randomized algorithm.

On the other hand, an application to PCP systems for NP suggests
that, if our techniques can substantially reduce the random bit
complexity of arbitrary probabilistic systems, then NP has
subexponential deterministic simulations.

ISSN 1433-8092 | Imprint