LIPIcs.ITCS.2023.88.pdf
- Filesize: 0.77 MB
- 20 pages
Document
Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP
Authors
Amol Pasarkar 
,
Mihalis Yannakakis
-
Part of:
Volume:
14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-02-01
File
Document Identifiers
Author Details
Cite AsGet BibTex
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)
https://doi.org/10.4230/LIPIcs.ITCS.2023.88
https://doi.org/10.4230/LIPIcs.ITCS.2023.88
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Complexity classes
Keywords
- Total Complexity
- Extremal Combinatorics
- Pigeonhole Principle
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 624-630, 2020.
-
Bèla Bollobàs. Extremal Graph Theory. Dover, 2013.
- David Conlon and Asaf Ferber. Lower bounds for multicolor ramsey numbers, 2020. URL: https://doi.org/10.48550/arXiv.2009.10458.
-
Michel Deza and Peter Frankl. Every large set of equidistant (0, +1, −1)-vectors forms a sunflower. Combinatorica, 1:225-231, September 1981.
-
P. Erdös and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, s1-35(1):85-90, 1960.
-
Paul W. Goldberg and Christos H. Papadimitriou. Towards a unified complexity theory of total functions. Journal of Computer and System Sciences, 94:167-192, 2018.
-
Ronald L Graham, Bruce L Rothschild, and Joel H Spencer. Ramsey theory, volume 20. 'John Wiley & Sons', 1990.
-
Emil Jeřábek. Integer factoring and modular square roots. Journal of Computer and System Sciences, 82(2):380-394, 2016.
-
David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of Computer and System Sciences, 37(1):79-100, 1988.
-
Stasys Jukna. Extremal Combinatorics With Applications in Computer Science. Springer Berlin, 2013.
-
Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos H. Papadimitriou. Total functions in the polynomial hierarchy. In 12th Innovations in Theoretical Computer Science Conference, ITCS, volume 185 of LIPIcs, pages 44:1-44:18, 2021.
-
Ilan Komargodski, Moni Naor, and Eylon Yogev. White-box vs. black-box complexity of search problems: Ramsey and graph property testing. J. ACM, 66(5), July 2019.
-
Nimrod Megiddo and Christos H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317-324, 1991.
-
Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994.
-
Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis. Ppp-completeness with connections to cryptography. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 148-158. IEEE Computer Society, 2018.