Clique is hard on average for unary Sherali-Adams
1Susanna F. de Rezende (Lund University)
https://simons.berkeley.edu/talks/susanna-f-de-rezende-lund-university-2023-04-18
Satisfiability: Theory, Practice, and Beyond
Given an Erdos-Renyi random graph G on n vertices where an edge is present with probability 1/2, with high probability the largest clique in the graph is of size approximately 2 log n. Clearly, there are proofs of size n^O(log n) that G has no larger clique by simply showing that all subsets of ＞ 2 log n vertices do not form a clique. While this naive proof is expected to be essentially optimal (up to constant factors in the exponent), proving a superpolynomial size lower bound is open even for resolution.
In this talk, I will present an overview of the proof that for G~G(n,1/2) with high probability, unary Sherali-Adams requires size n^Omega(log n) to refute the claim that G contains a k-clique, even for k=n^Omega(1). To obtain this result, we introduce a technique inspired by pseudo-calibration that involves defining a signed measure on monomials that captures the contribution of a monomial to a refutation. This measure intuitively represents progress and should have further applications in proof complexity.
This is joint work with Aaron Potechin and Kilian Risse.