Tight Size-Degree Bounds for Sums-of-Squares Proofs

Massimo Lauria, Jakob Nordström

We exhibit families of $4$-CNF formulas over $n$ variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) $d$ but require SOS proofs of size $n^…