###### Proof of 8.5.

We wish to prove $T$ is non-empty. First, recall that since $x\neq 0$ by
assumption, $|S|>0$. By Lemma 8.8, we then have $|S_{n}|>0$ as well. We now
argue that every vertex in $S_{n}$ is incident to at least one heavy edge.
Since $S_{n}$ is non-empty, this implies $T$ is non-empty as desired.

To see each vertex in $S_{n}$ has a heavy edge, recall the local view of each
normal vertex is a codeword in
$C_{A}\otimes\mathbb{F}_{2}^{B}+\mathbb{F}_{2}^{A}\otimes C_{B}$ with weight
less than $w=\Delta^{3/2-\varepsilon}$. Because the dual tensor code is
$w$-robust, each column (respectively row) is within
$\Delta^{1/2-\varepsilon}/\delta$ of a codeword in $C_{A}$ (respectively
$C_{B}$). Since these codes all have distance at least $\delta\Delta$, there
must be a row or column with at least
$\delta\Delta-\Delta^{1/2-\varepsilon}/\delta$ ones which exactly corresponds
to a heavy edge. We note this fact also implies the total number of heavy
edges is at least $|S_{n}|$, which will be useful later on. ∎

###### Proof of 8.6.

Now that we have confirmed the existence of $T$, we want to show it is
incident to many heavy edges. To do so, we’ll argue that $T$ is small compared
to the number of heavy edges.

To start, we show that $|T|\leq\frac{64}{\delta^{2}\Delta}|S|$. The proof is
the same as [61, Claim 11], but we give it here for completeness. First, note
that by the expander mixing lemma on $\mathcal{G}^{\cup}$ (which is the double
cover of a $4\sqrt{\Delta}$-spectral expander) we have:

$\displaystyle|E(S,T)|$
$\displaystyle\leq\frac{2\Delta}{|G|}|S||T|+4\sqrt{\Delta}\sqrt{|S||T|}$
$\displaystyle\leq\frac{2\Delta^{1/2-\varepsilon}}{3}|T|+4\sqrt{\Delta}\sqrt{|S||T|}$

where as in Lemma 8.8 we have again used the fact that

$\left|S\right|\leq\frac{4}{\delta\Delta}\left|x\right|\leq\frac{2}{3\Delta^{5/2+\varepsilon}}n=\frac{1}{3\Delta^{1/2+\varepsilon}}|G|.$

On the other hand, since each vertex $v\in T$ is incident to at least one
heavy edge $e$ by definition, $v$ (and $e$) are contained in at least
$\delta\Delta-\Delta^{1/2-\varepsilon}/\delta$ squares in $x$. Since each of
these contains an additional (unique) edge incident to $v$, we also have the
following lower bound

$|E(S,T)|\geq(\delta\Delta-\Delta^{1/2-\varepsilon}/\delta)|T|.$

Combining these inequalities one can check that
$|T|\leq\frac{64}{\delta^{2}\Delta}|S|$ for large enough $\Delta$ as desired.

With this in hand, recall from the proof of 8.5 that the total number of heavy
edges in $E_{x}$ is at least
$|S_{n}|\geq(1-\frac{64}{\Delta^{1-2\varepsilon}})|S|$ (where the inequality
is given by Lemma 8.8). Together, this implies the average number of heavy
edges incident to a vertex in $T$ is at least:

$\frac{|S_{n}|}{|T|}\geq\frac{\delta^{2}\Delta}{64}\left(1-\frac{64}{\Delta^{1-2\varepsilon}}\right)=:2\alpha\Delta.$
(13)

Finally given that the average degree is at least $2\alpha\Delta$, we want to
show there is some fraction of vertices with degree $\geq\alpha\Delta$. This
is immediate from recalling that the maximum degree of $\mathcal{G}^{\cup}$
(and thus $T$) is $2\Delta$, which implies at least an $\alpha/2$ fraction of
vertices in $T$ are incident to at least $\alpha\Delta$ heavy edges as
desired. ∎

###### Proof of 8.7.

Finally, we want to show there are few edges between $T$ and $S_{e}\cup
S_{v}$. This follows from the fact that both sets are small, and the
underlying graph $\mathcal{G}^{\cup}$ is the double cover of a
$4\sqrt{\Delta}$-expander on $|G|=\frac{2n}{\Delta^{2}}$ vertices. In
particular, combining the expander mixing lemma with our bounds from Lemma 8.8
gives:

$\displaystyle E(S_{e}\cup S_{v},T)$
$\displaystyle\leq\frac{2\Delta}{|G|}|S_{e}\cup
S_{v}||T|+4\sqrt{\Delta}\sqrt{|T||S_{e}\cup S_{v}|}$
$\displaystyle\leq\frac{128\Delta^{2\varepsilon}}{|G|}|S||T|+32\Delta^{\varepsilon}\sqrt{|T||S|}.$

Recall that $\left|S\right|\leq\frac{1}{3\Delta^{1/2+\varepsilon}}|G|$.
Further, since each normal vertex is adjacent to $T$ and the degree of $T$ is
at most $2\Delta$, we have
$(1-\frac{64}{\Delta^{1-2\varepsilon}})|S|\leq|S_{n}|\leq 2\Delta|T|$, and
thus for large enough $\Delta$ that $|S|\leq 4\Delta|T|$. Altogether we
therefore have:

$\displaystyle E(S_{e}\cup S_{v},T)$
$\displaystyle\leq\frac{128}{3\Delta^{1/2-\varepsilon}}|T|+64\Delta^{1/2+\varepsilon}|T|\leq\beta\Delta^{1/2+\varepsilon}|T|$

where $\beta=64+\frac{128}{3\Delta}$. As a result, at most an $\alpha/4$
fraction of vertices in $T$ are incident to more than
$d_{1}=\frac{4\beta}{\alpha}\Delta^{1/2+\varepsilon}$ vertices of $S_{e}\cup
S_{v}$ as desired, which completes the proof of 8.3 and Theorem 8.2 in turn. ∎

∎

∎

Putting everything together, we now prove the existence of an explicit family
of SS-HDX.

###### Proof of Theorem 8.1.

Fix any $r\in(0,1/2)$, $\varepsilon\in(0,1/2)$,
$\gamma\in(1/2+\varepsilon,1)$, and $\delta\in(0,1)$ satisfying
$-\delta\log\delta-(1-\delta)\log(1-\delta)<r$, and let
$\Delta=\Delta(r,\varepsilon/2,\gamma,\delta)\in\mathbb{N}$ be sufficiently
large that the guarantees of Corollary 7.9 and Theorem 8.2 are met. Brute
forcing over pairs of length $\Delta$ codes $C_{A},C_{B}$ of dimensions
$r\Delta$ and $(1-r)\Delta$ respectively, Corollary 7.9 promises we can find
in $O_{\Delta}(1)$ time codes $C_{A},C_{B}$ such that:

  1. 1.

$\dim C_{A}=\lfloor{r\Delta}\rfloor$ and $\dim C_{B}=\Delta-\dim C_{A}$,

  2. 2.

The distances of $C_{A},C_{B},C_{A}^{\perp},C_{B}^{\perp}$ are all at least
$\delta\Delta$,

  3. 3.

Both dual tensor codes $C_{0}^{\perp}=(C_{A}\otimes C_{B})^{\perp}$ and
$C_{1}^{\perp}=(C_{A}^{\perp}\otimes C_{B}^{\perp})^{\perp}$ are
$\Delta^{3/2-\varepsilon/2}$-robust with $\Delta^{\gamma}$-resistance to
puncturing.

  4. 4.

$C_{A},C_{B},C_{A}^{\perp}$, and $C_{B}^{\perp}$ have generator matrices where
every row and column have at least two ones.

Following the construction and the discussion earlier this section, the Tanner
maps resulting from these codes and the explicit left-right Cayley complexes
of [26] give an explicit family of chain complexes with degree between $3$ and
$2\Delta^{2}$ and non-trivial co-homology. Furthermore each individual complex
in the family satisfies the requirements of Theorem 8.2 in both directions, so
by symmetry the complexes are $(\rho_{1},\rho_{2})$-small-set HDX for
$\rho_{1}=\frac{\delta}{6\Delta^{3/2+\varepsilon}}$ and
$\rho_{2}=\frac{56}{\Delta^{3-2\varepsilon}}$. This concludes the proof of
Theorem 8.1. ∎

######  Remark 8.9.

We note that the proof of Theorem 8.2 actually gives a stronger guarantee than
small-set (co)-boundary expansion. In particular, because the boundary $y$
that reduces the weight of $x$ is supported on a local view of a single
vertex, the result actually gives an isoperimetric inequality for the broader
class of small, locally minimal functions:

$\forall x\in\mathbb{F}_{2}^{n}~{}\text{s.t. $x$ is locally minimal
and}~{}\left|x\right|\leq\rho_{1}n:\left|\delta_{1}x\right|\geq\rho_{2}\left|x\right|,$

where $x$ is locally minimal if
$\left|x\right|\leq\left|x+\delta_{0}(e_{v})\right|$ for all basis vectors
$e_{v}\in\mathbb{F}_{2}^{m}$. As discussed in Section 3.1, this stronger
isoperimetric inequality has seen prior use in the topological HDX literature
[47, 33, 49, 50] as well as in recent work on c3-LTCs [57] and qLDPC codes
[58].

## Acknowledgements

The authors thank Noah Fleming, Sam Hopkins, and Russell Impagliazzo for
helpful discussion on reductions within the Sum-of-Squares hierarchy, Amy
Kanne for helpful discussions on qLDPC codes and [61], and Tali Kaufman for
many fruitful discussions on high dimensional expansion. The authors also
thank Sam Hopkins, Shachar Lovett, and Anthony Ostuni for helpful comments on
an earlier version of the manuscript.

## References

  * AAT [05] Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis, _Towards strong nonapproximability results in the lovász-schrijver hierarchy_ , Proceedings of the thirty-seventh annual ACM symposium on theory of computing, 2005, pp. 294–303.
  * AC [88] Noga Alon and Fan RK Chung, _Explicit construction of linear sized tolerant networks_ , Discrete Mathematics 72 (1988), no. 1-3, 15–19.
  * AC [02] Noga Alon and Michael Capalbo, _Explicit unique-neighbor expanders_ , The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., IEEE, 2002, pp. 73–79.
  * AJT [19] Vedat Levi Alev, Fernando Granha Jeronimo, and Madhur Tulsiani, _Approximating constraint satisfaction problems on high-dimensional expanders_ , 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2019, pp. 180–201.
  * AL [20] Vedat Levi Alev and Lap Chi Lau, _Improved analysis of higher order random walks and applications_ , arXiv preprint arXiv:2001.02827 (2020).
  * Alo [86] Noga Alon, _Eigenvalues and expanders_ , Combinatorica 6 (1986), no. 2, 83–96.
  * ALO [20] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan, _Spectral independence in high-dimensional expanders and applications to the hardcore model_ , arXiv preprint arXiv:2001.00303 (2020).
  * ALOV [19] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant, _Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid_ , Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, pp. 1–12.
  * BBK+ [21] Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, and David Steurer, _Playing unique games on certified small-set expanders_ , STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 (Samir Khuller and Virginia Vassilevska Williams, eds.), ACM, 2021, pp. 1629–1642.
  * BCK [15] Boaz Barak, Siu On Chan, and Pravesh K Kothari, _Sum of squares lower bounds from pairwise independence_ , Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015, pp. 97–106.
  * BE [21] Nikolas P Breuckmann and Jens Niklas Eberhardt, _Quantum low-density parity-check codes_ , PRX Quantum 2 (2021), no. 4, 040101.
  * BGIP [01] Sam Buss, Dima Grigoriev, Russell Impagliazzo, and Toniann Pitassi, _Linear gaps between degrees for the polynomial calculus modulo distinct primes_ , Journal of Computer and System Sciences 62 (2001), no. 2, 267–289.
  * BGMT [12] Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani, _Sdp gaps from pairwise independence_ , Theory of Computing 8 (2012), no. 1, 269–289.
  * BHKL [21] Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett, _Hypercontractivity on high dimensional expanders_ , arXiv preprint arXiv:2111.09444 (2021).
  * BHKL [22] , _High dimensional expanders: Eigenstripping, pseudorandomness, and unique games_ , Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1069–1128.
  * BIK+ [96] Paul Beame, Russell Impagliazzo, Jan Krajíček, Toniann Pitassi, and Pavel Pudlák, _Lower bounds on hilbert’s nullstellensatz and propositional proofs_ , Proceedings of the London Mathematical Society 3 (1996), no. 1, 1–26.
  * BKS [18] Boaz Barak, Pravesh K Kothari, and David Steurer, _Small-set expansion in shortcode graph and the 2-to-2 conjecture_ , arXiv preprint arXiv:1804.08662 (2018).
  * BS [14] Boaz Barak and David Steurer, _Sum-of-squares proofs and the quest toward optimal algorithms_ , arXiv preprint arXiv:1404.5236 (2014).
  * BSW [99] Eli Ben-Sasson and Avi Wigderson, _Short proofs are narrow—resolution made simple_ , Proceedings of the thirty-first annual ACM symposium on Theory of computing, 1999, pp. 517–526.
  * CEI [96] Matthew Clegg, Jeffery Edmonds, and Russell Impagliazzo, _Using the groebner basis algorithm to find proofs of unsatisfiability_ , Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996, pp. 174–183.
  * Cha [16] Siu On Chan, _Approximation resistance from pairwise-independent subgroups_ , Journal of the ACM (JACM) 63 (2016), no. 3, 1–32.
  * CMM [09] Moses Charikar, Konstantin Makarychev, and Yury Makarychev, _Integrality gaps for sherali-adams relaxations_ , Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 283–292.
  * CS [96] A Robert Calderbank and Peter W Shor, _Good quantum error-correcting codes exist_ , Physical Review A 54 (1996), no. 2, 1098.
  * DD [19] Yotam Dikstein and Irit Dinur, _Agreement testing theorems on layered set systems_ , 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2019, pp. 1495–1524.
  * DDFH [18] Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha, _Boolean function analysis on high-dimensional expanders_ , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * DEL+ [21] Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes, _Locally testable codes with constant rate, distance, and locality_ , arXiv preprint arXiv:2111.04808 (2021).
  * DFHT [20] Irit Dinur, Yuval Filmus, Prahladh Harsha, and Madhur Tulsiani, _Explicit sos lower bounds from high-dimensional expanders_ , arXiv preprint arXiv:2009.05218 (2020).
  * DK [17] Irit Dinur and Tali Kaufman, _High dimensional expanders imply agreement expanders_ , 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 974–985.
  * [29] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra, _On non-optimally expanding sets in grassmann graphs_ , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 940–951.
  * [30] , _Towards a proof of the 2-to-1 games conjecture?_ , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 376–389.
  * DSW [06] Irit Dinur, Madhu Sudan, and Avi Wigderson, _Robust local testability of tensor products of ldpc codes_ , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, 2006, pp. 304–315.
  * EH [17] Lior Eldar and Aram W Harrow, _Local hamiltonians whose ground states are hard to approximate_ , 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 427–438.
  * EK [16] Shai Evra and Tali Kaufman, _Bounded degree cosystolic expanders of every dimension_ , Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 36–48.
  * EKZ [20] Shai Evra, Tali Kaufman, and Gilles Zémor, _Decodable quantum ldpc codes beyond the square root distance barrier using high dimensional expanders_ , 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2020, pp. 218–227.
  * FKP [19] Noah Fleming, Pravesh Kothari, and Toniann Pitassi, _Semialgebraic proofs and efficient algorithm design_ , Foundations and Trends in Theoretical Computer Science, 2019.
  * GLL [21] Tom Gur, Noam Lifshitz, and Siqi Liu, _Hypercontractivity on high dimensional expanders_ , arXiv preprint arXiv:2111.09375 (2021).
  * GMPT [10] Konstantinos Georgiou, Avner Magen, Toniann Pitassi, and Iannis Tourlakis, _Integrality gaps of 2-o(1) for vertex cover sdps in the lovász–schrijver hierarchy_ , SIAM Journal on Computing 39 (2010), no. 8, 3553–3570.
  * Gri [98] Dima Grigoriev, _Tseitin’s tautologies and lower bounds for nullstellensatz proofs_ , Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), IEEE, 1998, pp. 648–652.
  * [39] , _Complexity of positivstellensatz proofs for the knapsack_ , computational complexity 10 (2001), no. 2, 139–154.
  * [40] , _Linear lower bound on degrees of positivstellensatz calculus proofs for the parity_ , Theoretical Computer Science 259 (2001), no. 1-2, 613–622.
  * Gro [83] Mikhael Gromov, _Filling riemannian manifolds_ , Journal of Differential Geometry 18 (1983), no. 1, 1–147.
  * Gro [10] Mikhail Gromov, _Singularities, expanders and topology of maps. part 2: From combinatorics to topology via algebraic isoperimetry_ , Geometric and Functional Analysis 20 (2010), no. 2, 416–526.
  * HHO [21] Matthew B Hastings, Jeongwan Haah, and Ryan O’Donnell, _Fiber bundle codes: breaking the n 1/2 polylog (n) barrier for quantum ldpc codes_ , Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 1276–1288.
  * JMO+ [21] Fernando Granha Jeronimo, Tushant Mittal, Ryan O’Donnell, Pedro Paredes, and Madhur Tulsiani, _Explicit abelian lifts and quantum ldpc codes_ , arXiv preprint arXiv:2112.01647 (2021).
  * JST [21] Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani, _Near-linear time decoding of ta-shma’s codes via splittable regularity_ , Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 1527–1536.
  * Kho [02] Subhash Khot, _On the power of unique 2-prover 1-round games_ , Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, 2002, pp. 767–775.
  * KKL [14] Tali Kaufman, David Kazhdan, and Alexander Lubotzky, _Ramanujan complexes and bounded degree topological expanders_ , 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, IEEE, 2014, pp. 484–493.
  * KKL [16] , _Isoperimetric inequalities for ramanujan complexes and topological expanders_ , Geometric and Functional Analysis 26 (2016), no. 1, 250–287.
  * KM [18] Tali Kaufman and David Mass, _Cosystolic expanders over any abelian group._ , Electron. Colloquium Comput. Complex., vol. 25, 2018, p. 134.
  * KM [21] , _Unique-neighbor-like expansion and group-independent cosystolic expansion_ , 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * KMMS [18] Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra, _Small set expansion in the johnson graph._ , Electronic Colloquium on Computational Complexity (ECCC), vol. 25, 2018, p. 78.
  * KMOW [17] Pravesh K Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer, _Sum of squares lower bounds for refuting any csp_ , Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 132–145.
  * KMS [17] Subhash Khot, Dor Minzer, and Muli Safra, _On independent sets, 2-to-2 games, and grassmann graphs_ , Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 576–589.
  * KMS [18] , _Pseudorandom sets in grassmann graph have near-perfect expansion_ , 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2018, pp. 592–601.
  * KO [20] Tali Kaufman and Izhar Oppenheim, _High order random walks: Beyond spectral gap_ , Combinatorica (2020), 1–37.
  * KT [21] Tali Kaufman and Ran J. Tessler, _New cosystolic expanders from tensors imply explicit quantum LDPC codes with $\Omega(\sqrt{(}n)\log^{k}(n))$ distance_, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, 2021, pp. 1317–1329.
  * [57] Ting-Chun Lin and Min-Hsiu Hsieh, _c3-local testable codes from lossless expanders_ , arXiv preprint arXiv:2201.11369 (2022).
  * [58] , _Good quantum ldpc codes with linear time decoder from lossless expanders_ , arXiv preprint arXiv:2203.03581 (2022).
  * LM [06] Nathan Linial* and Roy Meshulam*, _Homological connectivity of random 2-complexes_ , Combinatorica 26 (2006), no. 4, 475–487.
  * LSV [05] Alexander Lubotzky, Beth Samuels, and Uzi Vishne, _Explicit constructions of ramanujan complexes of type ad_ , European Journal of Combinatorics 26 (2005), no. 6, 965–993.
  * LZ [22] Anthony Leverrier and Gilles Zémor, _Quantum tanner codes_ , arXiv preprint arXiv:2202.13641 (2022).
  * Mor [94] Moshe Morgenstern, _Existence and explicit constructions of q+ 1 regular ramanujan graphs for every prime power q_ , Journal of Combinatorial Theory, Series B 62 (1994), no. 1, 44–62.
  * MS [09] Claire Mathieu and Alistair Sinclair, _Sherali-adams relaxations of the matching polytope_ , Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 293–302.
  * [64] Pavel Panteleev and Gleb Kalachev, _Asymptotically good quantum and locally testable classical ldpc codes_ , arXiv preprint arXiv:2111.03654 (2021).
  * [65] , _Quantum ldpc codes with almost linear minimum distance_ , IEEE Transactions on Information Theory 68 (2021), no. 1, 213–229.
  * Pra [22] Kevin Pratt, Personal communication, March 2022.
  * RS [10] Prasad Raghavendra and David Steurer, _Graph expansion and the unique games conjecture_ , Proceedings of the forty-second ACM symposium on Theory of computing, 2010, pp. 755–764.
  * RST [12] Prasad Raghavendra, David Steurer, and Madhur Tulsiani, _Reductions between expansion problems_ , 2012 IEEE 27th Conference on Computational Complexity, IEEE, 2012, pp. 64–73.
  * Sch [08] Grant Schoenebeck, _Linear level lasserre lower bounds for certain k-csps_ , 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2008, pp. 593–602.
  * Ste [96] Andrew M Steane, _Error correcting codes in quantum theory_ , Physical Review Letters 77 (1996), no. 5, 793.
  * STT [07] Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani, _Tight integrality gaps for lovász-schrijver lp relaxations of vertex cover and max cut_ , Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, pp. 302–310.
  * Tan [81] R Tanner, _A recursive approach to low complexity codes_ , IEEE Transactions on information theory 27 (1981), no. 5, 533–547.
  * Tul [09] Madhur Tulsiani, _Csp gaps and reductions in the lasserre hierarchy_ , Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 303–312.
  * Tul [21] , _On sos algorithms and lower bounds for constraint satisfaction problems over high-dimensional expanders._ , SoS+TCS Reading Group, 2021.

##  Appendix A Existence of Good Base Codes

In this section we prove Corollary 7.9, the existence of base codes $C_{A}$
and $C_{B}$ with the properties needed for our SS-HDX construction in Theorem
8.1. We restate the result here for convenience.

######  Corollary A.1.

Fix $r\in(0,1/2)$, $\varepsilon\in(0,1/2)$, $\gamma\in(1/2+\varepsilon,1)$ and
$\delta>0$ satisfying $-\delta\log\delta-(1-\delta)\log(1-\delta)<r$. When $k$
is large enough, there exist codes $C_{A}$ and $C_{B}$ of length $\Delta$ such
that

  1. 1.

$\dim C_{A}=\lfloor{r\Delta}\rfloor$ and $\dim C_{B}=\Delta-\dim C_{A}$

  2. 2.

The distances of $C_{A},C_{B},C_{A}^{\perp},C_{B}^{\perp}$ are all at least
$\delta\Delta$

  3. 3.

Both dual tensor codes $C_{0}^{\perp}=(C_{A}\otimes C_{B})^{\perp}$ and
$C_{1}^{\perp}=(C_{A}^{\perp}\otimes C_{B}^{\perp})^{\perp}$ are
$\Delta^{3/2-\varepsilon}$-robust with $\Delta^{\gamma}$-resistance to
puncturing

  4. 4.

$C_{A},C_{B},C_{A}^{\perp}$, and $C_{B}^{\perp}$ have generator matrices where
every row and column have at least two ones.

###### Proof.

We assume for notational simplicity that $r\Delta$ and $(1-r)\Delta$ are
integral (the proof is essentially the same without this assumption). We will
argue that all four properties are satisfied with probability going to one (as
$\Delta$ becomes large) under some distribution for the generation of $C_{A}$
and $C_{B}$. By a union bound, a pair satisfying all properties must then
exist for large enough $\Delta$.

Consider the distribution over codes $C_{A}$ and $C_{B}$ given by generating
$C_{A}$ by a uniformly random $r\Delta\times\Delta$ generator matrix, and
$C_{B}^{\perp}$ from an independent uniformly random $r\Delta\times\Delta$
generator matrix. Leverrier and Zémor [61] prove that the first three
conditions occur with probability going to one under this distribution (see
[61, Theorem 17]), so we need only show the last condition holds.

This follows easily from a few basic observations. Let $r_{0}\in(0,1)$ be any
constant. First, observe that conditioned on being full rank, a uniformly
random $r_{0}\Delta\times\Delta$ generator matrix corresponds to a uniformly
random subspace of dimension $r_{0}\Delta$, and furthermore that such a matrix
is full rank with probability going to $1$ as $\Delta$ grows large. Second,
note that by a Chernoff and union bound, the probability this random generator
matrix has any row or column with less than two ones also quickly goes to
zero. This implies that for any fixed $r_{0}$, as $\Delta$ grows large the
probability that a random subspace of dimension $r_{0}\Delta$ has a generator
matrix satisfying condition $4$ goes to $1$.

Since $C_{A}$ and $C_{B}^{\perp}$ are generated by uniformly random
$r\Delta\times\Delta$ generator matrices, they clearly satisfy condition 4
with high probability. The trick is then simply to notice that (conditioned on
full rank), $C_{A}^{\perp}$ and $C_{B}$ are uniformly random subspaces of
dimension $(1-r)\Delta$, and therefore also satisfy condition $4$ with
probability going to one by the above observation. ∎