Clique is hard on average for unary Sherali-Adams
summary
Claim: for G~G(n,1/2) with high probability, unary Sherali‑Adams needs size n^{Omega(log n)} to refute the existence of a k‑clique even when k = n^{Omega(1)}. Proof builds a pseudo‑measure (signed measure on monomials) that lower‑bounds progress, decomposes rectangles into small/block pieces, and truncates Fourier characters to edge‑sets with vertex‑cover ≤ d. Main work is strong concentration over exponentially many rectangles using rich‑extension and small‑error set properties; result is encoding‑robust and even handles a polynomial‑vs‑2 log n gap.
AI-written summary · about
chapters (15)
- 0:00Intro
- 1:00Computational complexity of k-clique problem
- 1:34Proof complexity of k-clique problem
- 3:29Sherali-Adams (Sum-of-Monomials)
- 7:28Size lower bounds of n()
- 10:46Did exist one size lower bounds for algebraic proof systems
- 13:06How to prove uSA size lower bounds
- 14:59Clique formula Clique(G, k)
- 18:24Pseudo-measure is a measure of progress
- 20:12Expected behavior of a progress measure
- 21:03Decomposition of rectangles
- 24:17Defining the measure (failed attempts)
- 26:48Defining the measure (successful attempt)
- 30:12Well-behaved graphs (property of random G)
- 31:40Final remarks
related talks
23mVerifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach
24mA New Conjecture on Hardness of Low-Degree 2-CSP’s with...
32mCombinatorial Proofs of Concentration Bounds
01h 09mPlenary: Neighborhoods Banding Together: Reasoning Globally about Programs
40mUtilizing Structure in Combinatorial Solving and Reasoning
18mOn the Verification of a Subgraph Construction Algorithm
53mData Deduplication For Redundant Graph Structures Files
24mPolynomial-Time Program Equivalence for Machine Knitting