TR98-049 Authors: Dimitris Fotakis, Paul Spirakis

Publication: 30th August 1998 09:09

Downloads: 993

Keywords:

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.