Open Collections

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

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Mathematical logic and foundations; Theoretical computer science

video/mp4

Author affiliation: KTH Royal Institute of Technology

2020-07-22

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/75241

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/