{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:20Z","timestamp":1753894400200,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Stabbing Planes (also known as Branch and Cut) is a proof system introduced\nvery recently which, informally speaking, extends the DPLL method by branching\non integer linear inequalities instead of single variables. The techniques\nknown so far to prove size and depth lower bounds for Stabbing Planes are\ngeneralizations of those used for the Cutting Planes proof system. For size\nlower bounds these are established by monotone circuit arguments, while for\ndepth these are found via communication complexity and protection. As such\nthese bounds apply for lifted versions of combinatorial statements. Rank lower\nbounds for Cutting Planes are also obtained by geometric arguments called\nprotection lemmas.\n  In this work we introduce two new geometric approaches to prove size\/depth\nlower bounds in Stabbing Planes working for any formula: (1) the antichain\nmethod, relying on Sperner's Theorem and (2) the covering method which uses\nresults on essential coverings of the boolean cube by linear polynomials, which\nin turn relies on Alon's combinatorial Nullenstellensatz.\n  We demonstrate their use on classes of combinatorial principles such as the\nPigeonhole principle, the Tseitin contradictions and the Linear Ordering\nPrinciple. By the first method we prove almost linear size lower bounds and\noptimal logarithmic depth lower bounds for the Pigeonhole principle and\nanalogous lower bounds for the Tseitin contradictions over the complete graph\nand for the Linear Ordering Principle. By the covering method we obtain a\nsuperlinear size lower bound and a logarithmic depth lower bound for Stabbing\nPlanes proof of Tseitin contradictions over a grid graph.<\/jats:p>","DOI":"10.46298\/lmcs-20(1:1)2024","type":"journal-article","created":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T19:15:09Z","timestamp":1705000509000},"source":"Crossref","is-referenced-by-count":0,"title":["Depth lower bounds in Stabbing Planes for combinatorial principles"],"prefix":"10.46298","volume":"Volume 20, Issue 1","author":[{"given":"Stefan","family":"Dantchev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Galesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abdul","family":"Ghani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2024,1,11]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/12858\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/12858\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T19:15:10Z","timestamp":1705000510000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/10134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(1:1)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2102.07622v4","asserted-by":"subject"},{"id-type":"arxiv","id":"2102.07622v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2102.07622","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2102.07622","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2024,1,11]]},"article-number":"10134"}}