Explicit SoS Lower Bounds from Small-Set High Dimensional Expanders

Explore a groundbreaking lecture on explicit Sum-of-Squares (SoS) lower bounds derived from small-set high dimensional expanders. Delve into Max Hopkins' presentation at the Simons Institute, where he addresses the long-standing question of whether structured Constraint Satisfaction Problems (CSPs) exist whose unsatisfiability cannot be captured by SoS. Discover how the theory of high dimensional expansion leads to polynomial-time constructible XOR-families that are optimally hard for SoS. Learn about the novel concept of small-set high dimensional expanders (SS-HDX) and their construction through a new isoperimetric inequality for Square Cayley Complexes. Gain insights into the recent resolution of the c^3-LTC and qLDPC conjectures, and understand the implications of this work for the field of computational complexity.

Explicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders