期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 C1C, and an sC1, 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.
