Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP

Amol Pasarkar, Mihalis Yannakakis, Christos Papadimitriou

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…