Holographic Proofs and Derandomization Download as PS


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.