Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Abstract

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.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • Academy of Sciences of the Czech Republic
  • University of Copenhagen
  • KTH Royal Institute of Technology
  • Saint Petersburg State University
  • Institute of Russian Academy of Sciences
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Diskret matematik

Nyckelord

Originalspråkengelska
Titel på värdpublikationCCC '20: Proceedings of the 35th Computational Complexity Conference 2020
RedaktörerShubhangi Saraf
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektroniskt)9783959771566
StatusPublished - 2020 jul 1
PublikationskategoriForskning
Peer review utfördJa
Evenemang35th Computational Complexity Conference, CCC 2020 - Virtual, Online, Tyskland
Varaktighet: 2020 jul 282020 jul 31

Publikationsserier

NamnLeibniz International Proceedings in Informatics, LIPIcs
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volym169
ISSN (tryckt)1868-8969

Konferens

Konferens35th Computational Complexity Conference, CCC 2020
LandTyskland
OrtVirtual, Online
Period2020/07/282020/07/31