- Authors: D. van Melkebeek and R. Santhanam.
- Reference: SIAM Journal on Computing, 35: 59-90, 2005.
- Earlier version:
- R. Santhanam and D. van Melkebeek.
Holographic proofs and derandomization.
In Proceedings of the 18th Annual IEEE Conference
on Computational Complexity, pages 269-283, 2003.
Abstract
We derive a stronger consequence of EXP having
polynomial-size circuits than was known previously, namely that
for each language L in P,
and for each efficiently decidable error-correcting code E having
nontrivial relative distance, there is a simulation of L in
Merlin-Arthur polylogarithmic time that fools all deterministic
polynomial-time adversaries for inputs that are codewords of E.
Using the connection between circuit lower bounds and derandomization,
we obtain uniform assumptions for derandomizing BPP.
Our results strengthen the space-randomness tradeoffs of Sipser,
Nisan and Wigderson, and Lu.
We also consider a more quantitative notion of simulation, where the
measure of success of the simulation is the fraction of inputs of a
given length on which the simulation works. Among other results,
we show that if there is no polynomial time bound t such that P can
be simulated well by Merlin-Arthur machines operating in time t,
then for any ε > 0
there is a simulation of BPP in P that works for all but
2nε inputs of length n.
This is a uniform strengthening of a recent result of Goldreich and Wigderson.
Finally, we give an unconditional simulation of multitape Turing machines
operating in probabilistic time t by Turing machines operating in
deterministic time o(2t).
We show similar results for randomized NC1 circuits.
Our proofs are based on a combination of techniques in the theory of
derandomization with results on holographic proofs.
