BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Exponential Resolution Lower Bounds for the Weak Pigeonhole Principle over Sparse Graphs Risse, Kilian


Despite the fact that the resolution proof system has been extensively studied for decades, a full understanding of even some quite basic formulas has remained out of reach. One example of this are the so-called weak pigeonhole principle (PHP) formulas claiming that m pigeons can be mapped one-to-one to n holes for $m >> n$. In a breakthrough result, Raz (2001) established exponential lower bounds for such formulas, which Razborov further strengthened and generalized by developing his so-called pseudo-width method. In this work, we show how to extend the pseudo-witdth method further to obtain lower bounds for graph PHP formulas, where pigeons can only fly to holes as specified by sparse bipartite graphs, thus answering an open question by Razborov. This seminar is based on joint work with Susanna F. de Rezende, Jakob Nordström and Dmitry Sokolov.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International