Clique Is Hard on Average for Unary Sherali-Adams

• We prove that unary Sherali-Adams requires proofs of size nΩ(d) to rule out the existence of an nΘ(1)-clique in Erdős-Rényi random graphs whose maximum clique is of size d ≤ 2 log n. This lower bound is tight up to the multiplicative constant in the exponent. We obtain this result by introducing a technique inspired by pseudo-calibration which may be of independent interest. The technique involves defining a measure on monomials that precisely captures the contribution of a monomial to a refutation. This measure intuitively captures progress and should have further applications in proof complexity.

Subject headings

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Keyword

Clique

Proof Complexity

Unary Sherali Adams

Publication and Content Type

kon (subject category)

ref (subject category)