Abstract
In 2001, Grigoriev proved that random 3-XOR instances are hard to approximate for the powerful Sum-of-Squares semidefinite programming hierarchy, starting a long and fruitful line of work toward optimal SoS-hardness of random CSPs. In stark contrast, the landscape for *explicit* CSPs (Initiated by Grigoriev several years prior) remains almost entirely open. All known examples are either not hard to approximate (e.g. Tseitin formulas with soundness $1-o(1)$), or are otherwise captured by $O(\log(n))$-rounds of SoS (e.g. constructions from brute force search). This raises a natural question:
Are there structured CSPs whose unsatisfiability cannot be captured by SoS?
In this talk, we discuss the recent resolution of this question via the theory of high dimensional expansion. Building on work of Dinur, Filmus, Harsha, and Tulsiani, and Kaufman, Kazhdan, and Lubotzky, we introduce the notion of small-set high dimensional expanders (SS-HDX) and show they lead to poly-time constructible XOR-families that are essentially optimally hard for SoS. We then discuss how to explicitly construct SS-HDX via a new isoperimetric inequality for ``Square Cayley Complexes,’’ a family of non-simplicial chain complexes used in the recent resolution of the $c^3$-LTC and qLDPC conjectures.
Based on joint work with Ting-Chun (David) Lin.