Easiness assumptions and hardness tests: Trading time for zero error

Valentine Kabanets

Abstract

We propose a new approach towards derandomization in the uniform setting, where it is computationally hard to find possible mistakes in the simulation of a given probabilistic algorithm. The approach consists in combining both easiness and hardness complexity assumptions: if a derandomization method based on an easiness assumption fails, then we obtain a certain hardness test that can be used to remove error in BPP algorithms. As an application, we prove that every RP algorithm can be simulated by a zero-error probabilistic algorithm, running in expected subexponential time, that appears correct infinitely often (i.o.) to every efficient adversary. A similar result by Impagliazzo and Wigderson states that BPP allows deterministic subexponential-time simulations that appear correct with respect to any efficiently sampleable distribution i.o., under the assumption that EXP≠BPP; in contrast, our result does not rely on any unproven assumptions. As another application of our techniques, we get the following gap theorem for ZPP: either every RP algorithm can be simulated by a deterministic subexponential-time algorithm that appears correct i.o. to every efficient adversary, or EXP=ZPP. In particular, this implies that if ZPP is somewhat easy, e.g., ZPP⊆DTIME(2nc) for some fixed constant c, then RP is subexponentially easy in the uniform setting described above.

Versions