Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-059 | 16th April 2020 18:25

Pr-ZSUBEXP is not contained in Pr-RP

RSS-Feed




TR20-059
Authors: Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma
Publication: 27th April 2020 08:27
Downloads: 171
Keywords: 


Abstract:

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.
The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the win-win argument. We remark that even though the easy witness method is a key component in many celebrated results in derandomization, we are not aware of any previous unconditional separation like the one we show.

We remark that the result relativizes. We could not prove a similar result for total functions, nor for functions in ZTime(T(n)) for T(n) below a half-exponential function (i.e., T such that T(T(n)) < 2^n).



ISSN 1433-8092 | Imprint