Corelab Seminar
2011-2012
Antonis Antonopoulos (NTUA)
Formalizing Computational Indistinguishability: Derandomization of RP and AM
Abstract.
In a previous lecture we proved the first BPP Uniform Derandomization
Theorem (Impagliazzo-Wigderson '98). Now, we will try to clarify the notion of
Computational Indistinguishability, by defining appropriate "adversaries" called refuters,
trying to distinguish a language from another given certain computational abilities.
In this setting, Kabanet's enhanced I.W.'s idea by using also an easiness result, and proved
that every RP language can be simulated in deterministic subexponential time, so that this
simulation seems correct infinitely often to every zero-error probabilistic refuter.
If it fails, we can obtain a certain hardness test that can be used to remove error in
BPP algorithms. This provides a gap theorem for ZPP: Either every RP algorithm can
be simulated by a deterministic subexponential-time algorithm (under a certain setting),
or EXP=ZPP.
Also, Chi-Jen Lu proved that either AM=NP, or NP is contained in deterministic
subexponential time (with respect to any nondeterministic polynomial-time refuter)
infinitely often. This implies that the Graph Non-isomorphism Problem (GNI) has i.o.
subexponential-size proofs, which is the first non-trivial derandomization result
without any complexity assumption! This technique can be also used to obtain
some significant time vs. space tradeoffs.
We'll discuss thoroughly the setting, the intuitive part of the
proofs, and the significance & implications of these results to our view of Complexity Theory.