Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-059 | 1st June 2020 16:29

Pr-ZSUBEXP is not contained in Pr-RP

RSS-Feed




Revision #1
Authors: Gonen Krak, Noam Parzanchevski, Rahul Santhanam, Amnon Ta-Shma
Accepted on: 1st June 2020 16:29
Downloads: 473
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. Rahul Santhanam showed us a very simple proof that proves a stronger claim. In this revision we give this proof



Changes to previous version:

Rahul Santhanam showed us a very simple proof that proves a stronger claim. In this revision we give this proof


Paper:

TR20-059 | 16th April 2020 18:25

Pr-ZSUBEXP is not contained in Pr-RP





TR20-059
Authors: Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma
Publication: 27th April 2020 08:27
Downloads: 807
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