Clique Is Hard on Average for Unary Sherali-Adams

De Rezende, Susanna F.Lund University,Lunds universitet,Parallella System,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Parallel Systems,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH (författare)

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.

Potechin, AaronUniversity of Chicago (författare)
Risse, KilianSwiss Federal Institute of Technology(Swepub:lu)ki0404ri (författare)
Parallella SystemInstitutionen för datavetenskap (creator_code:org_t)

Ingår i:Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023, s. 12-250272-54289798350318944

Av författaren/redakt...: De Rezende, Susa ...; Potechin, Aaron; Risse, Kilian

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.