ECCC-Report TR20-059https://eccc.weizmann.ac.il/report/2020/059Comments and Revisions published for TR20-059en-usMon, 01 Jun 2020 16:29:39 +0300
Revision 1
| Pr-ZSUBEXP is not contained in Pr-RP |
Gonen Krak,
Noam Parzanchevski,
Amnon Ta-Shma,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2020/059#revision1We 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 proofMon, 01 Jun 2020 16:29:39 +0300https://eccc.weizmann.ac.il/report/2020/059#revision1
Paper TR20-059
| Pr-ZSUBEXP is not contained in Pr-RP |
Gonen Krak,
Noam Parzanchevski,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2020/059We 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).Mon, 27 Apr 2020 08:27:15 +0300https://eccc.weizmann.ac.il/report/2020/059