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