Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-086 | 8th June 2023 12:53

Random $(\log n)$-CNF are Hard for Cutting Planes (Again)


Authors: Dmitry Sokolov
Publication: 8th June 2023 16:55
Downloads: 286


The random $\Delta$-CNF model is one of the most important distribution over $\Delta\text{-}\mathrm{SAT}$ instances. It is closely connected to various areas of computer science, statistical physics, and is a benchmark for satisfiability algorithms. Fleming, Pankratov, Pitassi, and Robere and independently Hrubes and Pudlak showed that when $\Delta = \Theta(\log n)$, any Cutting Planes proof for random $\Delta$-CNF on $n$ variables requires size $2^{n / \mathrm{polylog} n}$ in the regime where the number of clauses guarantees that the formula is unsatisfiable with high probability. In this paper we show tight lower bound $2^{\Omega(n)}$ on size CP-proofs for random $(\log n)$-CNF formulas. Moreover, our proof is much simpler and self-contained in contrast with previous results based on Jukna's lower bound for monotone circuits.

ISSN 1433-8092 | Imprint