Standard

Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs. / de Rezende, Susanna F.; Nordström, Jakob; Risse, Kilian; Sokolov, Dmitry.

35th Computational Complexity Conference, CCC 2020. ed. / Shubhangi Saraf. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. 28 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 169).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

de Rezende, SF, Nordström, J, Risse, K & Sokolov, D 2020, Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs. in S Saraf (ed.), 35th Computational Complexity Conference, CCC 2020., 28, Leibniz International Proceedings in Informatics, LIPIcs, vol. 169, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 35th Computational Complexity Conference, CCC 2020, Virtual, Online, Germany, 28/07/20. https://doi.org/10.4230/LIPIcs.CCC.2020.28

APA

de Rezende, S. F., Nordström, J., Risse, K., & Sokolov, D. (2020). Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs. In S. Saraf (Ed.), 35th Computational Complexity Conference, CCC 2020 [28] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 169). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CCC.2020.28

Vancouver

de Rezende SF, Nordström J, Risse K, Sokolov D. Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs. In Saraf S, editor, 35th Computational Complexity Conference, CCC 2020. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2020. 28. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.CCC.2020.28

Author

de Rezende, Susanna F. ; Nordström, Jakob ; Risse, Kilian ; Sokolov, Dmitry. / Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs. 35th Computational Complexity Conference, CCC 2020. editor / Shubhangi Saraf. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. (Leibniz International Proceedings in Informatics, LIPIcs).

BibTeX

@inproceedings{7b2a4204f149415e9084c85ac35b0024,
title = "Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs",
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.",
keywords = "Perfect matching, Proof complexity, Resolution, Sparse graphs, Weak pigeonhole principle",
author = "{de Rezende}, {Susanna F.} and Jakob Nordstr{\"o}m and Kilian Risse and Dmitry Sokolov",
note = "Funding Information: Funding The authors were funded by the Knut and Alice Wallenberg grant KAW 2016.0066. In addition, the second author was supported by the Swedish Research Council grant 2016-00782 and the Independent Research Fund Denmark (DFF) grant 9040-00389B, and the fourth author by the Knut and Alice Wallenberg grant KAW 2016.0433. Part of this work was carried out while visiting the Simons Institute for the Theory of Computing in association with the DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity, which is conducted with support from the National Science Foundation. Publisher Copyright: {\textcopyright} Susanna F. de Rezende, Jakob Nordstr{\"o}m, Kilian Risse, and Dmitry Sokolov; licensed under Creative Commons License CC-BY 35th Computational Complexity Conference (CCC 2020). Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 35th Computational Complexity Conference, CCC 2020 ; Conference date: 28-07-2020 Through 31-07-2020",
year = "2020",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.CCC.2020.28",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Shubhangi Saraf",
booktitle = "35th Computational Complexity Conference, CCC 2020",
address = "Germany",

}

RIS

TY - GEN

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

AU - de Rezende, Susanna F.

AU - Nordström, Jakob

AU - Risse, Kilian

AU - Sokolov, Dmitry

N1 - Funding Information: Funding The authors were funded by the Knut and Alice Wallenberg grant KAW 2016.0066. In addition, the second author was supported by the Swedish Research Council grant 2016-00782 and the Independent Research Fund Denmark (DFF) grant 9040-00389B, and the fourth author by the Knut and Alice Wallenberg grant KAW 2016.0433. Part of this work was carried out while visiting the Simons Institute for the Theory of Computing in association with the DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity, which is conducted with support from the National Science Foundation. Publisher Copyright: © Susanna F. de Rezende, Jakob Nordström, Kilian Risse, and Dmitry Sokolov; licensed under Creative Commons License CC-BY 35th Computational Complexity Conference (CCC 2020). Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/7/1

Y1 - 2020/7/1

N2 - 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.

AB - 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.

KW - Perfect matching

KW - Proof complexity

KW - Resolution

KW - Sparse graphs

KW - Weak pigeonhole principle

UR - http://www.scopus.com/inward/record.url?scp=85089398484&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CCC.2020.28

DO - 10.4230/LIPIcs.CCC.2020.28

M3 - Conference contribution

AN - SCOPUS:85089398484

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 35th Computational Complexity Conference, CCC 2020

A2 - Saraf, Shubhangi

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 35th Computational Complexity Conference, CCC 2020

Y2 - 28 July 2020 through 31 July 2020

ER -

ID: 75310335