On the Complexity of Avoiding Heavy Elements

We introduce and study the following natural total search problem, which we call the heavy element avoidance (Heavy Avoid) problem: for a distribution on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> bits specified by a Boolean circuit sampling it, and for some parameter <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\delta(N)\geq 1/$</tex> poly <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(N)$</tex> fixed in advance, output an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> -bit string that has probability less than <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\delta(N)$</tex>. We show that the complexity of Heavy Avoid is closely tied to frontier open questions in complexity theory about uniform randomized lower bounds and derandomization. Among other results, we show: 1)For a wide range of circuit classes <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{C}$</tex>, including <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\text{ACC}^{0}, \text{TC}^{0},\text{NC}^{1}$</tex> and general Boolean circuits, EX P does not have uniform randomized C-circuits if and only if Heavy Avoid for uniform implicit C -samplers has efficient deterministic algorithms infinitely often. This gives the first algorithmic characterization of lower bounds for EXP against uniform randomized low-depth circuits. We show similar algorithmic characterizations for lower bounds in PSPACE, NP and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\text{EXP}^{\text{NP}}$</tex>. 2)Unconditionally, there are polynomial-time pseudodeterministic algorithms that work infinitely often for several variants of Heavy Avoid, such as for uniform samplers of small randomness complexity. In contrast, the existence of a similar algorithm that solves Heavy Avoid for arbitrary polynomial-time samplers would solve a long-standing problem about hierarchies for probabilistic time. 3)If there is a time and depth efficient deterministic algorithm for Heavy Avoid, then <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$BPP=P$</tex>. Without the depth-efficiency requirement in the assumption, we still obtain a non-trivial form of infinitely-often deterministic simulation of randomized algorithms. These results are shown using non-black-box reductions, and we argue that the use of non-black-box reductions is essential here. The full version is available on ECCC [1].