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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International