Randomized separations in black-box TFNP
For researchers in computational complexity, this work provides a unified method to upgrade deterministic separations to randomized ones in the black-box TFNP setting, which is a significant theoretical advance.
The paper develops a general technique to show that deterministic and randomized black-box reducibility are equivalent for reductions from complete problems in several TFNP subclasses (PPP, PPAD, PPA, t-PPP) to any TFNP problem, thereby strengthening all known black-box separations from these classes to randomized separations.
We study the relationship between deterministic and randomized black-box reducibility between problems in TFNP. Our main contribution is a general technique that establishes equivalence between these reducibility types from specific TFNP problems to any TFNP problem. In particular, we show that this equivalence holds for reductions from complete problems in PPP, PPAD, PPA, and $t$-PPP. In turn, it strengthens all known black-box separations, originating from these classes, to randomized separations.