  We prove that Sherali-Adams with polynomially bounded coefficients requires
proofs of size $n^{\Omega(d)}$ to rule out the existence of an
$n^{\Theta(1)}$-clique in Erd\H{o}s-R\'{e}nyi random graphs whose maximum
clique is of size $d\leq 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.
