DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2023.88

Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP

Authors: Amol Pasarkar, Christos Papadimitriou, and Mihalis Yannakakis

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

We study the complexity of computational problems arising from existence theorems in extremal combinatorics. For some of these problems, a solution is guaranteed to exist based on an iterated application of the Pigeonhole Principle. This results in the definition of a new complexity class within TFNP, which we call PLC (for "polynomial long choice"). PLC includes all of PPP, as well as numerous previously unclassified total problems, including search problems related to Ramsey’s theorem, the Sunflower theorem, the Erdős-Ko-Rado lemma, and König’s lemma. Whether the first two of these four problems are PLC-complete is an important open question which we pursue; in contrast, we show that the latter two are PPP-complete. Finally, we reframe PPP as an optimization problem, and define a hierarchy of such problems related to Turàn’s theorem.

Cite as

Amol Pasarkar, Christos Papadimitriou, and Mihalis Yannakakis. Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 88:1-88:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{pasarkar_et_al:LIPIcs.ITCS.2023.88,
  author =	{Pasarkar, Amol and Papadimitriou, Christos and Yannakakis, Mihalis},
  title =	{{Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{88:1--88:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.88},
  URN =		{urn:nbn:de:0030-drops-175913},
  doi =		{10.4230/LIPIcs.ITCS.2023.88},
  annote =	{Keywords: Total Complexity, Extremal Combinatorics, Pigeonhole Principle}
}

Search Results

Documents authored by Pasarkar, Amol

Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP

Abstract

Cite as

Thanks for your feedback!

Could not send message