Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-022 | 1st October 2021 16:16

Depth lower bounds in Stabbing Planes for combinatorial principles

RSS-Feed




Revision #1
Authors: Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
Accepted on: 1st October 2021 16:16
Downloads: 66
Keywords: 


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 established via communication complexity arguments. As such they work for the lifted version 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.



Changes to previous version:

Fixed a bug in the lower bound for Tseitin over the grid graph.


Paper:

TR21-022 | 20th February 2021 21:59

Depth lower bounds in Stabbing Planes for combinatorial principles





TR21-022
Authors: Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin
Publication: 20th February 2021 22:20
Downloads: 207
Keywords: 


Abstract:

We prove logarithmic depth lower bounds in Stabbing Planes for the classes of combinatorial principles known as the Pigeonhole principle and the Tseitin contradictions. The depth lower bounds are new, obtained by giving almost linear length lower bounds which do not depend on the bit-size of the inequalities and in the case of the Pigeonhole principle are tight.

The technique known so far to prove depth lower bounds for Stabbing Planes is a generalization of that used for the Cutting Planes proof system. In this work we introduce two new approaches to prove length/depth lower bounds in Stabbing Planes: one relying on Sperner's Theorem which works for the Pigeonhole principle and Tseitin contradictions over the complete graph; a second proving the lower bound for Tseitin contradictions over a grid graph, which uses a result on essential coverings of the boolean cube by linear polynomials, which in turn relies on Alon's combinatorial Nullenstellensatz



ISSN 1433-8092 | Imprint