ECCC-Report TR21-043https://eccc.weizmann.ac.il/report/2021/043Comments and Revisions published for TR21-043en-usThu, 18 Mar 2021 20:14:27 +0200
Paper TR21-043
| Promise Problems Meet Pseudodeterminism |
Peter Dixon,
A. Pavan,
N. V. Vinodchandran
https://eccc.weizmann.ac.il/report/2021/043The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high probability. Recently, it was shown that such an algorithm would imply that every approximation algorithm can be made pseudodeterministic (Dixon, Pavan, Vinodchandran; (ITCS 2021).
The main conceptual contribution of this work is to establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally connected to the relationship between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: every promise problem in PromiseBPP has a solution in BPP if and only if APEP has a pseudodeterministic algorithm. Based on this intuition, we show that pseudodeterministic algorithms for APEP can shed light on a few central topics in complexity theory such as circuit lowerbounds, probabilistic hierarchy theorems, and multi-pseudodeterminism.Thu, 18 Mar 2021 20:14:27 +0200https://eccc.weizmann.ac.il/report/2021/043