Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NIKOLAJ SCHWARTZBACH:
All reports by Author Nikolaj Schwartzbach:

TR22-128 | 11th September 2022
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubacek, Alon Rosen, Nikolaj Schwartzbach

PPP-Completeness and Extremal Combinatorics

Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erdos-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard; here "implicit" means that the collection is represented ... more >>>




ISSN 1433-8092 | Imprint