Random Walks, Conditional Hitting Sets and Partial Derandomization
Dimitris A. Fotakis, Paul G. Spirakis · 1998
. 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 ` C, and an s 62 C 1 , we suggest to exploit s for constructing a hitting set for 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 substantiall...