We initiate the study of complexity classes ${A^B}$ where ${A}$ and ${B}$ are both ${TFNP}$ subclasses. For example, we consider complexity classes of the form ${PPP^{PPP}}$, ${PPAD^{PPA}}$, and ${PPA^{PLS}}$. We define complete problems for such classes, and show that they belong in ${TFNP}$. These definitions require some care, since ... more >>>

A problem $\mathcal{P}$ is considered downward self-reducible, if there exists an efficient algorithm for $\mathcal{P}$ that is allowed to make queries to only strictly smaller instances of $\mathcal{P}$. Downward self-reducibility has been well studied in the case of decision problems, and it is well known that any downward self-reducible problem ... more >>>

We study the problem of finding multicollisions, that is, the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil A/B \rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = ... more >>>