Explicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
summary
Constructs poly-time constructible XOR-families whose unsatisfiability Sum-of-Squares cannot refute until linear-round SoS lower bounds, matching the Grigoriev random-instance hardness up to the completeness caveat (soundness bounded away from 1; boosting to 1/2+ε uses PCP reductions). Method builds SS-HDX (small-set high-dimensional expanders) via Square Cayley Complexes / chain complexes drawn from quantum LDPC code technology, proves completeness by translating SOS to XOR-refutation width and showing small-set boundary expansion (co-systolic distance) holds; the explicit constructions are efficient and achieve the claimed gaps.
AI-written summary · about
chapters (11)
- 0:00Introduction to SOS
- 3:04Defining 3XOR and SOS
- 7:11Hardness of approximation
- 10:31Historical context
- 14:01Explicit hard constructions
- 19:54Boundary expansion motivation
- 23:55Boundary operator and proof
- 29:36Refutation width
- 36:16Completeness via expansion
- 43:22Subspace and co-boundary
- 51:55High-dimensional expansion
related talks
58mSNARGs for P/poly from SIS
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits
47mPlanted Clique, Sum-of-Squares and Pseudo-Calibration
33mSecret Sharing, Slice Formulas, and Monotone Real Circuits
23mSmall-Box Cryptography
17mImproved Hardness of BDD and SVP Under Gap-(S)ETH
16mOn Oracles and Algorithmic Methods for Proving Lower Bounds
01h 01mLocal Proofs Approaching the Witness Length