  We construct an explicit family of 3-XOR instances hard for
$\Omega(n)$-levels of the Sum-of-Squares (SoS) semi-definite programming
hierarchy. Not only is this the first explicit construction to beat brute force
search (beyond low-order improvements (Tulsiani 2021, Pratt 2021)), combined
with standard gap amplification techniques it also matches the (optimal)
hardness of random instances up to imperfect completeness (Grigoriev TCS 2001,
Schoenebeck FOCS 2008).
  Our result is based on a new form of small-set high dimensional expansion
(SS-HDX) inspired by recent breakthroughs in locally testable and quantum LDPC
codes. Adapting the recent framework of Dinur, Filmus, Harsha, and Tulsiani
(ITCS 2021) for SoS lower bounds from the Ramanujan complex to this setting, we
show any (bounded-degree) SS-HDX can be transformed into a highly unsatisfiable
3-XOR instance that cannot be refuted by $\Omega(n)$-levels of SoS. We then
show Leverrier and Z\'emor's (Arxiv 2022) recent qLDPC construction gives the
desired explicit family of bounded-degree SS-HDX. Incidentally, this gives the
strongest known form of bi-directional high dimensional expansion to date.
