TY - JOUR
T1 - Derandomizing Arthur-Merlin Games using Hitting Sets
AU - Miltersen, Peter Bro
AU - Vinodchandran, N. V.
PY - 2005
Y1 - 2005
N2 - We prove that AM (and hence Graph Nonisomorphism) is in NP if for some ε > 0, some language in NE ∩ coNE requires nondeterministic circuits of size 2ε n This improves results of Arvind and Köbler and of Klivans and van Melkebeek who proved the same conclusion, but under stronger hardness assumptions. The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim’s hitting set approach to derandomization. As a spin-off, we show that this approach is strong enough to give an easy proof of the following implication: for some ε > 0, if there is a language in E which requires nondeterministic circuits of size 2ε n , then P = BPP. This differs from Impagliazzo and Wigderson’s theorem “only” by replacing deterministic circuits with nondeterministic ones.
AB - We prove that AM (and hence Graph Nonisomorphism) is in NP if for some ε > 0, some language in NE ∩ coNE requires nondeterministic circuits of size 2ε n This improves results of Arvind and Köbler and of Klivans and van Melkebeek who proved the same conclusion, but under stronger hardness assumptions. The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim’s hitting set approach to derandomization. As a spin-off, we show that this approach is strong enough to give an easy proof of the following implication: for some ε > 0, if there is a language in E which requires nondeterministic circuits of size 2ε n , then P = BPP. This differs from Impagliazzo and Wigderson’s theorem “only” by replacing deterministic circuits with nondeterministic ones.
U2 - 10.1007/s00037-005-0197-7
DO - 10.1007/s00037-005-0197-7
M3 - Journal article
SN - 1093-0159
VL - 14
SP - 256
EP - 279
JO - I E E E Conference on Computational Complexity. Proceedings
JF - I E E E Conference on Computational Complexity. Proceedings
IS - 3
ER -