__
TR23-086 | 8th June 2023 12:53
__

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

**Abstract:**
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.