Rahul Santhanam (University of Chicago):
Holographic Proofs and Derandomization
Nisan, using results of Babai, Fortnow and Lund on holographic proofs,
showed that if EXP has polynomial-size circuits, then EXP = MA, where MA
is the class of languages that have constant-round Merlin-Arthur
protocols. We strengthen this result by "scaling down" - we show that if
EXP has polynomial-size circuits then there is a simulation of P by
Merlin-Arthur protocols running in polylogarithmic time. Via the
connection between circuit lower bounds and derandomization, we obtain
uniform assumptions for derandomization of probabilistic decision
procedures. Similar tradeoffs hold between simulations of NP by
polylogarithmic-time Merlin-Arthur protocols and nontrivial simulations of
probabilistic decision procedures in nondeterministic time.
We also consider a different notion of simulation based on the fraction of
inputs on which the simulation suceeds, and show tradeoffs between
simulations of P by Merlin-Arthur protocols running in a fixed polynomial
time bound t and simulations of probabilistic polynomial-time in P.
Finally, we show that probabilistic time t on multi-tape Turing machines
can be simulated unconditionally in deterministic time o(2^t).
This is joint work with Dieter van Melkebeek.