2026-07-23T20:56:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27084 2026-07-23T11:36:20Z ddc:004 open_access

Randomized Separations in Black-Box TFNP Kiselev, Fedor TFNP Pigeonhole Principle 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor Kiselev 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.42 urn:nbn:de:0030-drops-270840 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.42 eng https://creativecommons.org/licenses/by/4.0/legalcode