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.