Explicit SoS lower bounds from high-dimensional expanders
summary
Constructs deterministic, polynomial-time Max-3-XOR instances from Ramanujan complexes whose true optimum is at most 1 − μ (μ a fixed constant, e.g. ~0.1) yet the Sum-of-Squares SDP hierarchy up to √(log n) levels still fails to refute and certifies full satisfiability. Proof combines XOR-resolution width lower bounds (Grigoriev/Shen), topological filling bounds (Gromov) on the complex, cosystolic expansion to get soundness via cohomology, and an explicit edge-variable encoding; the construction is explicit and the gap is essentially one versus 1 − μ for those SOS levels.
AI-written summary · about