{"ID":2890418,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.19108","arxiv_id":"2507.19108","title":"Downward self-reducibility in the total function polynomial hierarchy","abstract":"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 must lie in $\\mathsf{PSPACE}$. Harsha, Mitropolsky and Rosen [ITCS, 2023] initiated the study of downward self reductions in the case of search problems. They showed the following interesting collapse: if a problem is in $\\mathsf{TFNP}$ and also downward self-reducible, then it must be in $\\mathsf{PLS}$. Moreover, if the problem admits a unique solution then it must be in $\\mathsf{UEOPL}$. We demonstrate that this represents just the tip of a much more general phenomenon, which holds for even harder search problems that lie higher up in the total function polynomial hierarchy ($\\mathsf{TFΣ_i^P}$). In fact, even if we allow our downward self-reduction to be much more powerful, such a collapse will still occur. We show that any problem in $\\mathsf{TFΣ_i^P}$ which admits a randomized downward self-reduction with access to a $\\mathsf{Σ_{i-1}^P}$ oracle must be in $\\mathsf{PLS}^{\\mathsf{Σ_{i-1}^P}}$. If the problem has \\textit{essentially unique solutions} then it lies in $\\mathsf{UEOPL}^{\\mathsf{Σ_{i-1}^P}}$. As one (out of many) application of our framework, we get new upper bounds for the problems $\\mathrm{Range Avoidance}$ and $\\mathrm{Linear Ordering Principle}$ and show that they are both in $\\mathsf{UEOPL}^{\\mathsf{NP}}$.","short_abstract":"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 do...","url_abs":"https://arxiv.org/abs/2507.19108","url_pdf":"https://arxiv.org/pdf/2507.19108v1","authors":"[\"Karthik Gajulapalli\",\"Surendra Ghentiyala\",\"Zeyong Li\",\"Sidhant Saraogi\"]","published":"2025-07-25T09:45:36Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}