Skip to main content

Research Repository

Advanced Search

Depth lower bounds in Stabbing Planes for combinatorial principles

Dantchev, Stefan; Galesi, Nicola; Ghani, Abdul; Martin, Barnaby

Depth lower bounds in Stabbing Planes for combinatorial principles Thumbnail


Authors

Nicola Galesi



Abstract

Stabbing Planes (also known as Branch and Cut) is a proof system introduced very recently which, informally speaking, extends the DPLL method by branching on integer linear inequalities instead of single variables. The techniques known so far to prove size and depth lower bounds for Stabbing Planes are generalizations of those used for the Cutting Planes proof system. For size lower bounds these are established by monotone circuit arguments, while for depth these are found via communication complexity and protection. As such these bounds apply for lifted versions of combinatorial statements. Rank lower bounds for Cutting Planes are also obtained by geometric arguments called protection lemmas. In this work we introduce two new geometric approaches to prove size/depth lower bounds in Stabbing Planes working for any formula: (1) the antichain method, relying on Sperner's Theorem and (2) the covering method which uses results on essential coverings of the boolean cube by linear polynomials, which in turn relies on Alon's combinatorial Nullenstellensatz. We demonstrate their use on classes of combinatorial principles such as the Pigeonhole principle, the Tseitin contradictions and the Linear Ordering Principle. By the first method we prove almost linear size lower bounds and optimal logarithmic depth lower bounds for the Pigeonhole principle and analogous lower bounds for the Tseitin contradictions over the complete graph and for the Linear Ordering Principle. By the covering method we obtain a superlinear size lower bound and a logarithmic depth lower bound for Stabbing Planes proof of Tseitin contradictions over a grid graph.

Citation

Dantchev, S., Galesi, N., Ghani, A., & Martin, B. (2024). Depth lower bounds in Stabbing Planes for combinatorial principles. Logical Methods in Computer Science, 20(1), 1-19. https://doi.org/10.46298/lmcs-20%281%3A1%292024

Journal Article Type Article
Acceptance Date Nov 5, 2023
Online Publication Date Jan 11, 2024
Publication Date 2024-01
Deposit Date Apr 2, 2024
Publicly Available Date Apr 2, 2024
Journal Logical Methods in Computer Science
Print ISSN 1860-5974
Publisher Logical Methods in Computer Science
Peer Reviewed Peer Reviewed
Volume 20
Issue 1
Pages 1-19
DOI https://doi.org/10.46298/lmcs-20%281%3A1%292024
Keywords General Computer Science; Theoretical Computer Science
Public URL https://durham-repository.worktribe.com/output/2367754

Files




You might also like



Downloadable Citations