- 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
2^{nε} 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*(2^{t}).
We show similar results for randomized NC^{1} circuits.

Our proofs are based on a combination of techniques in the theory of
derandomization with results on holographic proofs.