DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.42

Randomized Separations in Black-Box TFNP

Authors: Fedor Kiselev

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

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.

Cite as

Fedor Kiselev. Randomized Separations in Black-Box TFNP. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kiselev:LIPIcs.CCC.2026.42,
  author =	{Kiselev, Fedor},
  title =	{{Randomized Separations in Black-Box TFNP}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.42},
  URN =		{urn:nbn:de:0030-drops-270840},
  doi =		{10.4230/LIPIcs.CCC.2026.42},
  annote =	{Keywords: TFNP, Pigeonhole Principle}
}

Search Results

Documents authored by Kiselev, Fedor

Randomized Separations in Black-Box TFNP

Abstract

Cite as

Thanks for your feedback!

Could not send message