Search

Your search keyword '"F.2.2, F.1.3, I.2.3, F.4.1"' showing total 2 results
Start Over Descriptor "F.2.2, F.1.3, I.2.3, F.4.1"
2 results on '"F.2.2, F.1.3, I.2.3, F.4.1"'

1. Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

Author

de Rezende, Susanna F., Nordström, Jakob, Risse, Kilian, and Sokolov, Dmitry

Subjects
Computer Science - Computational Complexity, Computer Science - Logic in Computer Science, Mathematics - Combinatorics, F.2.2, F.1.3, I.2.3, F.4.1, F.2.2, F.1.3, I.2.3, F.4.1
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.

Published
2019

2. Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

Author

de Rezende, Susanna F., Nordström, Jakob, Risse, Kilian, Sokolov, Dmitry, and Saraf, Shubhangi

Subjects
FOS: Computer and information sciences, F.2.2, F.1.3, I.2.3, F.4.1, weak pigeonhole principle, Computer Science - Logic in Computer Science, F.2.2, F.1.3, I.2.3, F.4.1, perfect matching, Computational Complexity (cs.CC), Computer Science::Computational Complexity, FOS: Mathematics, proof complexity, Mathematics - Combinatorics, Perfect matching, resolution, Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Theory of computation → Proof complexity, Weak pigeonhole principle, Combinatorics (math.CO), Proof complexity, Resolution, Sparse graphs, sparse graphs, MathematicsofComputing_DISCRETEMATHEMATICS
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.

Published
2020
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results