Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-017 | 23rd January 2024 11:00

On Pigeonhole Principles and Ramsey in TFNP



The generalized pigeonhole principle says that if tN + 1 pigeons are put into N holes then there must be a hole containing at least t + 1 pigeons. Let t-PPP denote the class of all total NP-search problems reducible to finding such a t-collision of pigeons. We introduce a new hierarchy of classes defined by the problems t-PPP. In addition to being natural problems in TFNP, we show that classes in and above the hierarchy are related to the notion of multi-collision resistance in cryptography, and contain the problem underlying the breakthrough average-case quantum advantage result shown by Yamakawa & Zhandry (FOCS 2022).
Finally, we give lower bound techniques for the black-box versions of t-PPP for any t. In particular, we prove that RAMSEY is not in t-PPP, for any t that is sub-polynomial in log(N), in the black-box setting. Goldberg and Papadimitriou conjectured that RAMSEY reduces to 2-PPP, we thus refute it and more in the black-box setting. We also provide an ensemble of black-box separations which resolve the relative complexity of the t-PPP classes with other well-known TFNP classes.

ISSN 1433-8092 | Imprint