文章基本信息

标题：Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
本地全文：下载
作者：Susanna F. de Rezende ; Jakob Nordstr{"o}m ; Kilian Risse 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：169
页码：28:1-28:24
DOI：10.4230/LIPIcs.CCC.2020.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the regime between balanced constant-degree expanders as in [Ben-Sasson and Wigderson '01] and highly unbalanced, dense graphs as in [Raz '04] and [Razborov '03, '04]. We obtain our results by revisiting Razborovâs pseudo-width method for PHP formulas over dense graphs and extending it to sparse graphs. This further demonstrates the power of the pseudo-width method, and we believe it could potentially be useful for attacking also other longstanding open problems for resolution and other proof systems.
关键词：proof complexity; resolution; weak pigeonhole principle; perfect matching; sparse graphs