@inproceedings{413fcb64-aede-4dfc-9b73-1677aa22ec0d,
  abstract     = {{We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem has found prominence due to its fundamental connections to derandomization, catalytic computing, and the metamathematics of complexity theory, among other areas.<br/><br/>While TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP class assuming that NP is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box TFNP to randomized proof systems and randomized reductions.<br/><br/>Next, we turn to developing a taxonomy of TFZPP problems. We highlight a problem called Nephew, originating from an infinity axiom in set theory. We show that Nephew is in PWPP∩ TFZPP and conjecture that it is not reducible to Lossy-Code. Intriguingly, except for some artificial examples, most other black-box TFZPP problems that we are aware of reduce to Lossy-Code:  <br/><br/>- We define a problem called Empty-Child capturing finding a leaf in a rooted (binary) tree, and show that this problem is equivalent to Lossy-Code. We also show that a variant of Empty-Child with "heights" is complete for the intersection of SOPL and Lossy-Code. <br/><br/>- We strengthen Lossy-Code with several combinatorial inequalities such as the AM-GM inequality. Somewhat surprisingly, we show the resulting new problems are still reducible to Lossy-Code. A technical highlight of this result is that they are proved by formalizations in bounded arithmetic, specifically in Jeřábek’s theory APC₁ (JSL 2007).<br/><br/>- Finally, we show that the Dense-Linear-Ordering problem reduces to Lossy-Code.}},
  author       = {{Fleming, Noah and Grosser, Stefan and Jain, Sigghartha and Li, Jiawei and Ren, Hanlin and Shirley, Morgan and Yuan, Weiqiang}},
  booktitle    = {{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)}},
  editor       = {{Saraf, Shubhangi}},
  isbn         = {{978-3-95977-410-9}},
  issn         = {{1868-8969}},
  language     = {{eng}},
  pages        = {{1--60}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{Leibniz International Proceedings in Informatics (LIPIcs)}},
  title        = {{Total search problems in ZPP}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.ITCS.2026.60}},
  doi          = {{10.4230/LIPIcs.ITCS.2026.60}},
  volume       = {{362}},
  year         = {{2026}},
}