  The 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.
