Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jiawei Li:

TR24-017 | 23rd January 2024
Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun

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 ... more >>>

ISSN 1433-8092 | Imprint