Corelab Seminar

Antonis Antonopoulos (NTUA)
Formalizing Computational Indistinguishability: Derandomization of RP and AM

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.