On Pigeonhole Principles and Ramsey in TFNP

• DOI: 10.48550/arxiv.2401.12604
• Publication Date: 2024-01-01
• Authors: Siddhartha Jain; Jiawei Li; Robert Robere; Zhiyang Xun
• Keywords: Pigeonhole principle; Black box; Ramsey's theorem

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 pigeons. Let t-PPP denote the class of all total NP-search problems reducible to finding such t-collision We introduce new hierarchy classes defined by t-PPP. In addition being natural in TFNP, we show and above related notion multi-collision resistance cryptography, contain problem underlying breakthrough average-case quantum advantage result shown Yamakawa & Zhandry (FOCS 2022). Finally, give lower bound techniques for black-box versions any t. particular, prove RAMSEY is not t-PPP, sub-polynomial log (N), setting. Goldberg Papadimitriou conjectured reduces 2-PPP, thus refute it more also provide an ensemble separations which resolve relative complexity with other well-known TFNP classes.