Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
<|reference_start|>Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients: 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.<|reference_end|>
@article{de rezende2024clique,
    title={Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients},
    author={Susanna F. de Rezende, Aaron Potechin, Kilian Risse},
    journal={arXiv preprint arXiv:2404.16722},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.16722},
    primaryClass={cs.CC}
}