by Prahladh Harsha

The last year (2021–22) has seen some amazing new constructions of locally testable codes with constant rate and constant fractional distance and testable with a constant number of queries, sometimes referred to as \(c^3\) LTCs [DELLM22, PK22]. The construction of Panteleev and Kalachev’s LTCs [PK22] is almost identical to that of Dinur, Evra, Livne, Lubotzky, and Mozes [DELLM22]; while Dinur et al.’s main goal was to construct \(c^3\) LTCs, Panteleev and Kalachev were motivated by considerations of constructing quantum LDPC codes. In this short note, I give an informal description of some of the ideas that led to the \(c^3\) LTC construction of Dinur et al., focusing more on the interplay between high-dimensional expanders and codes that led to this construction and less on the technical proofs. The original paper of [DELLM22] is extremely well written, and the reader is encouraged to read either the paper for the technical details or Goldreich’s exposition [Gol21] for a less group-theoretic presentation.

What are locally testable codes (LTCs)?

Let us begin by recalling what a code is. A code \(\mathcal{C}\) with blocklength over the Boolean alphabet refers to a subset of \(\{0,1\}^n\), and the elements of \(\mathcal{C}\) are usually referred to as codewords. The rate of the code \(\mathcal{C}\), denoted by \(R(\mathcal{C})\), is \(\frac{\log_2|\mathcal{C}|}{n}\) while the (fractional) distance, denoted by \(\delta(\mathcal{C})\), is the minimum fractional Hamming distance between any two distinct codewords in \(\mathcal{C}\). In this note, we will restrict our attention to linear codes: where the underlying alphabet \(\{0,1\}\) is identified with the field \(GF(2)\) and the code \(\mathcal{C}\) is a \(GF(2)\)-vector-space. In this case, the distance \(\delta\) is the minimum fractional weight of a nonzero codeword in \(\mathcal{C}\). If a code \(\mathcal{C}\) is linear, it can easily be described by the set of (dual) constraints that describe the vector space \(\mathcal{C}\). These constraints are usually referred to as parity checks. If, furthermore, each of these parity checks has constant arity (i.e., each constraint involves only a constant number of codeword locations), then the code is said to be a low-density parity-check code (LDPC). Given a string \(x \in \{0,1\}^n\) and a subset \(Q \subset [n]\) of the coordinate locations, \(x|_Q\) refers to the projection of the string \(x\) to the coordinates in \(Q\). The projected code \(\mathcal{C}|_Q\) is defined as the set of projected codewords, formally, \[\mathcal{C}|_Q := \{ x \in \{0,1\}^Q \colon \exists y \in \{0,1\}^{[n]\setminus Q} \text{ such that } (x,y) \in \mathcal{C}\}.\]

A linear code \(\mathcal{C}\) is said to be \(q\)-locally testable¹ if there exists a distribution \(\mathcal{Q}\) over subsets \(Q \subset [n]\) of size at most \(q\) such that the following is satisfied. \[\text{For every } x \in \{0,1\}^n, \text{ we have } \Pr_{Q \sim \mathcal{Q}}[ x|_Q \not\in \mathcal{C}|_Q] = \Omega(\delta(x,\mathcal{C})).\] Here, \(\delta(x,\mathcal{C})\) refers to \(\min_{c \in \mathcal{C}}\delta(x,c)\), the fractional Hamming distance between \(x\) and the code \(\mathcal{C}\).

In general, we will be interested in constructing a family \(\{\mathcal{C}_n\}_{n=1}^{\infty}\) of codes with increasing blocklengths. The holy grail in this area, which was attained by the recent constructions, was to obtain a family of codes that had constant rate and constant fractional distance and were testable with a constant number of queries. Codes that satisfy the first two properties (constant rate and constant fractional distance) are usually referred to as good codes. We will first take a detour and see how good codes are constructed and then return to the question of \(c^3\) LTCs.

Good codes and their construction

A family \(\{\mathcal{C}_n\}_n\) of codes is said to be good if there exist constants \(R, \delta \in (0,1)\) such that for all codes \(\mathcal{C}_n\) in the family, we have \(R(\mathcal{C}_n) \geq R\) and \(\delta(\mathcal{C}_n) \geq \delta\) (in other words, the rate and distance of all codes in the family are at least a constant, independent of the blocklength \(n\)).

How does one construct good codes? Classical constructions of good codes are typically obtained by constructing good codes over large alphabets and then concatenating them repeatedly to obtain good codes over the Boolean alphabet. In the early 1990s, Sipser and Spielman [SS96] gave a surprisingly simple and direct construction of good codes using expander graphs.

Expander graphs: Informally, a graph is a vertex expander if every not-too-large set of vertices has a large neighborhood. A handy way to certify that a given graph is a vertex expander is via the second-largest eigenvalue (in absolute value) of the normalized adjacency matrix of the graph. For any regular graph, the smaller this second-largest eigenvalue is, the better is the vertex expansion of the graph. Motivated by this, we will call a graph a \(\lambda\)-spectral-expander for some \(\lambda \in (0,1)\) if this second-largest eigenvalue is bounded above by \(\lambda\).

For the purpose of this note, it will be convenient to study expander graphs that arise from group actions. Such graphs are referred to as Schreier graphs, of which Cayley graphs are a special case. What is a group action? Given a group \(G\) and a set \(X\), the group is said to act on \(X\) if for each \(g \in G\) there exists a permutation \(\sigma_g \colon X \to X\) such that \(\sigma_{gh} = \sigma_g \circ \sigma_h\). In other words, each group element \(g\) induces a permutation on the set \(X\), and these permutations behave well with the group operation. This group action, denoted by \(\sigma\), is said to be transitive if for every \(x, y \in X\), there exists a \(g \in G\) such that \(\sigma_g(x) = y\). Let \(G\) be a finite group and \(X\) any finite set on which \(G\) acts transitively. Let \(S \subset G\) be a set of generators of \(G\) (closed under inverses). The Schreier graph of \(G\) on \(X\), denoted by \(\mathop{\mathrm{Sch}}(X,G,S)\), is the undirected graph whose vertices are the elements of \(X\), and \((x,y)\) is an edge if there exists \(s \in S\) such that \(L_s(x) = y\). Observe that \(\mathop{\mathrm{Sch}}(X,G,S)\) is an \(|S|\)-regular graph. The most commonly studied Schreier graphs are Cayley graphs where the underlying set \(X\) is the group \(G\) itself and the group action is either left or right multiplication (i.e., \(L_g(h) = gh\) and \(R_g(h) = hg\)). The corresponding Schreier graphs then are simply denoted as \(\mathop{\mathrm{Cay}}_L(G,S)\) and \(\mathop{\mathrm{Cay}}_R(G,S)\), respectively.

Let \(\mathcal{G}= (\mathcal{V}, \mathcal{E}) = \mathop{\mathrm{Sch}}(X,G,S)\) be a Schreier graph and \(\mathcal{C}\subset \{0,1\}^S\) be a code of blocklength \(|S|\). We think of the code \(\mathcal{C}\) as a “small” code; it has blocklength \(|S|\). Using this code and the graph \(\mathcal{G}\), we will build a “large” code on the edges \(\mathcal{E}\) of the graph \(\mathcal{G}\). This construction is due to Tanner, and in his honor, these codes are called Tanner codes. Formally, the Tanner code \(\mathop{\mathrm{Tan}}(\mathcal{G}, \mathcal{C})\) is the code consisting of codewords \(c \colon \mathcal{E}\to \{0,1\}\) satisfying the following constraints: \[\label{eq:tanner} \text{ For every } x \in \mathcal{V}, \text{ we have } c|_{N(x)} \in \mathcal{C}. \tag{1}\] Here, \(N(x)\) refers to the set of \(|S|\) neighbors of \(x\) in \(\mathcal{G}\). The [1] constraint, referred to as the Tanner constraint, states that “locally” the large code behaves like the “small” code around each vertex. Thus, the Tanner construction “lifts” the small code to the large code.

It is easy to observe that if \(\mathcal{C}\) has rate \(R \in (\frac12,1)\), then \(\mathop{\mathrm{Tan}}(\mathcal{G},\mathcal{C})\) has a rate of at least \(2R-1\). Furthermore and more importantly, Sipser and Spielman showed that if \(\mathcal{G}\) is a \(\lambda\)-spectral-expander and \(\mathcal{C}\) is a code with distance \(\delta\), then the Tanner code \(\mathop{\mathrm{Tan}}(\mathcal{G},\mathcal{C})\) has distance at least \(\delta (\delta-\lambda)\). Thus, the Tanner construction literally lifts the rate and distance of the small code to the large code, provided the graph \(\mathcal{G}\) is a good expander.

This yields the following extremely elegant construction of a family of good codes. Let \(G\) be a group and \(S\) a set of generators (closed under inverses) of \(G\). Let \(\{X_n\}\) be a growing family of finite sets on which the group \(G\) acts transitively. Let \(\{\mathcal{G}_n\}_n\) be the corresponding growing family of Schreier graphs \(\mathcal{G}_n = \mathop{\mathrm{Sch}}(X_n, G,S)\). If \(\mathcal{G}_n\) is a family of \(\lambda\)-spectral-expanders and \(\mathcal{C}\) is a constant size (of blocklength \(|S|\)) with rate \(R\) and distance \(\lambda\) satisfying \(R \in (\frac12,1)\) and \(\delta \in (\lambda, 1)\), then \(\mathop{\mathrm{Tan}}(\mathcal{G}_n,\mathcal{C})\) is a family of codes with rate \(2R-1\) and distance \(\delta (\delta – \lambda)\). Informally stated, the Sipser-Spielman construction uses the expansion properties of the graphs \(\mathcal{G}_n\) to lift the good-code property of the fixed-size code \(\mathcal{C}\) to yield a family of good codes.

Locally testable codes — a brief history

LTCs have been implicitly studied in theoretical computer science for more than three decades, starting from the early works on program checking and proof verification. Works on program checking led Blum, Luby, and Rubinfeld [BLR93] to show that the Hadamard code is 3-locally testable, while early works on proof verification led Rubinfeld and Sudan to show that the Reed-Muller code is locally testable with a sublinear (albeit superconstant) number of queries. These initial works on specific LTC constructions (namely Hadamard and Reed-Muller codes) led to the proof of the celebrated PCP theorem. With hindsight, it is easy to see that LTCs form the combinatorial backbone of PCP constructions. Not surprisingly, subsequent improvements in PCP constructions led to improved LTC constructions. In fact, until recently, the state-of-the-art LTC constructions with constant fractional distance and testable with constant queries, but with inverse polylogarithmic rate, mirrored the corresponding PCP constructions of Ben-Sasson-Sudan and Dinur [BS08, Din07]. There have been more direct LTC constructions that don’t use the PCP machinery; however, they are based on very similar techniques (recursion) and don’t yield any better parameters.

One may wonder then if the expander-based construction of good codes à la Sipser-Spielman could be modified to yield testability with constant queries. If one uses standard expander construction (in fact, a random graph), one can show that the underlying constraints are independent and that the corresponding code will require at least a linear number of queries to test [BHR05]. In fact, Spielman in his thesis [Spi95] states the following potential recipe for \(c^3\) LTCs:

One possible way of doing this would be to develop a carefully controlled construction of expander codes in which there is high redundancy among the constraints, but we do not know how to achieve a constant factor of redundancy. Another advantage of adding redundancy to the constraints is that this would increase the rate of the codes without affecting their error-correction ability. Thus, we feel that the problems of constructing testable expander codes and better expander codes are intertwined with the problem of finding expander codes with highly redundant constraints.

But how does one add these controlled redundancies without destroying the rate of the underlying Tanner code? In particular, how does one construct expander graphs such that the corresponding Tanner constraints given by [1] are redundant? This remained an open problem for nearly two decades until the importance of high-dimensional expanders in code constructions was understood.

LTCs and HDXs

High-dimensional expanders (HDXs) refer to a particular generalization of expander graphs to higher dimensions (or hypergraphs)². Kaufman and Lubotzky [KL14] were the first to observe the interplay between high-dimension expansion and testability. With the benefit of hindsight, one can restate the proofs of testability of the Hadamard and Reed-Muller codes in the language of high-dimensional expansion: more precisely, their testability is a direct consequence of the high-dimensional expansion of the Grassmannian complex. With this improved understanding, efforts were made to construct expander graphs using high-dimensional expanders with highly redundant Tanner constraints as prescribed by Spielman. In fact, in joint work with Dikstein, Dinur, and Ron-Zewi [DDHR20], we laid out a recipe for lifting the “local” local testability of a constant-size code to the “global” local testability of a family of codes, à la Sipser-Spielman. However, we did not know how to instantiate this recipe with a specific HDX and code to obtain the final LTC. A summer cluster on HDXs and error-correcting codes was organized at the Simons Institute³ precisely to understand this interplay between these two objects: HDXs and codes. One of the successes of that summer cluster was that the work initiated there eventually led to the Dinur et al. construction of \(c^3\) LTCs.

Just as expanders were used by Sipser-Spielman to lift the good-code property of a fixed code to a family of codes, Dinur et al. used HDXs (in particular the left-right Cayley complexes, which we will shortly define) to lift the testability of a fixed code to a family of codes leading to the \(c^3\) LTC construction.

The left-right Cayley complex

Inspired by the idea of extending the Schreier graph construction of expander graphs with redundancies, let us do the following. Let \(X\) be an underlying set acted on by two different groups, \(G_L\) and \(G_R\), with group actions \(L\) and \(R\), respectively. Let \(\mathcal{G}_L = \mathop{\mathrm{Sch}}(X,G_L,A)\) and \(\mathcal{G}_R =\mathop{\mathrm{Sch}}(X,G_R,B)\) be the corresponding two Schreier graphs, where \(A\) and \(B\) are sets of generators for \(G_L\) and \(G_R\), respectively. More precisely, \((x,y)\) is an edge in \(\mathcal{G}_L\) if \(y = L_a(x)\) for some \(a \in A\) while \((x,z)\) is an edge in \(\mathcal{G}_R\) if \(z = R_b(x)\) for some \(b \in B\). Let us further assume that the two group operations \(L\) and \(R\) commute. More precisely, for any \(a \in A\) and \(b \in B\) and any \(x\in X\), suppose that \[\label{eq:commute} R_b(L_a(x)) = L_a(R_b(x)). \tag{2}\] This lets us define 4-cycles in the graph \(\mathcal{G}= \mathcal{G}_L \cup \mathcal{G}_R\) as follows: for each \(x \in X\), we have a 4-cycle \((x, L_a(x), R_b(L_a(x))=L_a(R_b(x)), R_b(x))\) consisting of the four edges \((x,L_a(x)), (R_b(x), L_a(R_b(x))) \in E(\mathcal{G}_L)\) and \((x,R_b(x)), (L_a(x), R_b(L_a(x))) \in E(\mathcal{G}_R)\). This 4-cycle is generated by the triple \((x;a,b)\). Observe that the same 4-cycle is also generated by the triples \((L_a(x); a^{-1}, b), (R_b(x); a, b^{-1})\), and \((L_a(R_b(x)); a^{-1}, b^{-1})\). We will identify all these 4-cycles as the same square under the equivalence \(\sim\). Thus, the set of squares is given by \((X \times A \times B)/\sim\).

We are now ready to define the square complex. Let \(X\) be a finite set with two groups \(G_L\) and \(G_R\) acting transitively on it via the actions \(L\) and \(R\), respectively, that commute (i.e., satisfy [2]). We can now define a (commuting) square complex \(\mathcal{X}= (\mathcal{V}, \mathcal{E}, \mathcal{S})\) whose set of vertices, edges, and squares are defined as follows: the set \(\mathcal{V}\) of vertices is \(X\), and the set \(\mathcal{E}\) of edges is the union of edges in \(\mathcal{E}(\mathcal{G}_L)\) and \(\mathcal{E}(\mathcal{G}_R)\), while the set \(\mathcal{S}\) of squares is \((X \times A \times B)/\sim\).

Do such commuting square complexes exist? Yes, if we consider the two Schreier graphs corresponding to the two Cayley graphs \(\mathop{\mathrm{Cay}}_L(G,A)\) and \(\mathop{\mathrm{Cay}}_R(G,B)\) with left and right multiplication group actions, respectively. Clearly, the two group actions commute since \((ax)b = axb = a(xb)\). To avoid degeneracies, we may further assume that the set of generators \(A\) and \(B\) satisfy the “no-conjugacy condition”: namely, that for every \(a \in A, b\in B, g \in G\), we have \(ag \neq gb\). We will refer to the square complex formed in this manner from two Cayley graphs on the same underlying group with respect to left and right multiplication group actions as the left-right Cayley complex \(\mathcal{X}(G, A,B)\).

To see how the square complex allows for various redundant constraints, it will help to understand the following substructures within the complex.

Link of an edge

Let \(e = (x, L_a(x))\in \mathcal{E}\) be an edge in the square complex \(\mathcal{X}= (\mathcal{V}, \mathcal{E}, \mathcal{S})\) for some \(x \in \mathcal{V}\) and \(a \in A\). The link of \(e\), denoted by \(\mathcal{X}_e\), is the set of all squares that have the edge \(e\). More precisely, the square \((x, L_a(x),R_b(L_a(x)), R_b(x))\) given by \((x; a, b)\) for every \(b \in B\) belongs to \(\mathcal{X}_e\). Links of edges of the form \((x, R_b(x))\) are defined similarly.

Link of a vertex

Let \(x \in \mathcal{V}\) be a vertex in the square complex \(\mathcal{X}= (\mathcal{V}, \mathcal{E}, \mathcal{S})\). The link of \(x\), denoted by \(\mathcal{X}_x\), is the set of all squares that contain the vertex \(x\). More precisely, the square \((x, L_a(x),R_b(L_a(x)), R_b(x))\) given by \((x; a, b)\) for every \(a\in A\) and \(b \in B\) belongs to \(\mathcal{X}_x\). Observe that the link \(\mathcal{X}_x\) of any vertex \(x\) is in 1-1 correspondence with the grid \(A \times B\): the link \(\mathcal{X}_x\) contains a square \((x; a,b)\) for each \(a \in A\) and \(b\in B\).

It will be convenient (and fun) to visualize the link \(\mathcal{X}_e\) as a book whose spine is the edge \(e\) and whose pages are the squares that contain \(e\). Note that this is no ordinary book but rather a fantastic book: every square is a page in four different books corresponding to the four different edges of the square. Continuing this fantastic analogy, we can view the vertex links \(\mathcal{X}_x\) as bookshelves with \(|A|\) books along its column and \(|B|\) books along its row, with the restriction that the \(a^{th}\) book in the column shares a common page with the \(b^{th}\) book in the row. We can continue this analogy and view the different bookshelves (aka vertex links) in the square complex intersecting each other. The square complex thus looks like a library complex at Hogwarts with myriad intersections. It is these intersections that offer the redundancies in the edifice over which the code is constructed.

To describe the code, we need a few more ingredients: the base codes and their tensor product.

Base codes:

We will need two fixed-length codes \(\mathcal{C}_A\) and \(\mathcal{C}_B\) of blocklengths \(|A|\) and \(|B|\), respectively, over the binary alphabet. Let us assume that both these codes have distance \(\delta\) and rate \(R\).

Tensor-product code:

We will work with the tensor-product code \(\mathcal{C}_A \otimes \mathcal{C}_B\) with blocklength \(|A| \times |B|\), which is defined as follows: a word \(c \in \{0,1\}^{A\times B}\) is a codeword of the tensor-product code \(\mathcal{C}_A \otimes \mathcal{C}_B\) if for every \(a \in A\), we have \(c|_{(a, \cdot)} \in \mathcal{C}_B\) and for every \(b \in B\), we have \(c|_{(\cdot, b)} \in \mathcal{C}_A\). Thus, the codewords of \(\mathcal{C}_A \otimes \mathcal{C}_B\) reside in a grid such that each column is a codeword of \(\mathcal{C}_B\) while each row is a codeword of \(\mathcal{C}_A\).

Robust testability of tensor-product codes:

A natural tester exists for every tensor-product code: with probability half, pick either a random column or row, and check whether the restriction of the word to the chosen column (or row) is a column codeword (or row codeword). This test does not necessarily work for all tensor-product codes [Val05]. However, it is known that if the base codes \(\mathcal{C}_A\) and \(\mathcal{C}_B\) satisfy certain basic properties, then the above tester is a good tester [DSW06, BV09]. We will assume that the base codes \(\mathcal{C}_A\) and \(\mathcal{C}_B\) and their tensor-product code satisfy the following: for every word \(w \in \{0,1\}^{A \times B}\), we have \[\label{eq:tensor} \delta(w, \mathcal{C}_A \otimes \mathcal{C}_B) \leq \tau\cdot\frac{\mathop{\mathrm{{\mathbb{E}}}}_{a \in A}\left[\delta(w|_{(a,\cdot)}, \mathcal{C}_B)\right] + \mathop{\mathrm{{\mathbb{E}}}}_{b \in B}\left[\delta(w|_{(\cdot,b)}, \mathcal{C}_A)\right]}2, \tag{3}\] for some \(\tau \in (0,1)\), which is referred to as robustness of the tensor-product test. The condition described in [3] states that if on average the local views \(w|_{(a,\cdot)}\) and \(w|_{(\cdot,b)}\) are close to the corresponding codes \(\mathcal{C}_B\) and \(\mathcal{C}_A\), respectively, then the global word \(w\) is also close to the tensor-product code \(\mathcal{C}_A\otimes\mathcal{C}_B\) and \(\tau\) measures the relative deterioration in this closeness.

We are now ready to describe the code of Dinur, Evra, Livne, Lubotzky, and Mozes. Or to continue with the Harry Potter analogy, we are now ready to describe what are the legal codewords that can be transcribed on the pages of the books in the Hogwarts library complex.

The final code construction: Let \(\mathcal{X}= (\mathcal{V}, \mathcal{E}, \mathcal{S})\) be a square complex constructed from the Schreier graphs \(\mathop{\mathrm{Sch}}(X,G_L,A)\) and \(\mathop{\mathrm{Sch}}(X,G_R,B)\). Let \(\mathcal{C}_A, \mathcal{C}_B\) be two base codes and \(\mathcal{C}_A \otimes \mathcal{C}_B\) be their tensor product. Then, the code \(\mathcal{C}(\mathcal{X};\mathcal{C}_A,\mathcal{C}_B)\) is a code with blocklength \(|\mathcal{S}|\) defined as follows: \(c \in \{0,1\}^\mathcal{S}\) is a codeword if for each vertex \(x \in \mathcal{V}(\mathcal{X})\), we have that \[\label{eq:ltest} c|_{\mathcal{X}_x} \in \mathcal{C}_A \otimes \mathcal{C}_B. \tag{4}\]

It is easy to show that if the base codes \(\mathcal{C}_A\) and \(\mathcal{C}_B\) have rate \(R \in (\frac34,1)\), then the final code \(\mathcal{C}(\mathcal{X};\mathcal{C}_A,\mathcal{C}_B)\) has rate at least \(4R-3\). Furthermore, if the Schreier graphs \(\mathop{\mathrm{Sch}}(X,G_L,A)\) and \(\mathop{\mathrm{Sch}}(X,G_R,B)\) are \(\lambda\)-spectral-expanders and the base codes \(\mathcal{C}_A\) and \(\mathcal{C}_B\) have distance \(\delta\), then the final code \(\mathcal{C}(\mathcal{X};\mathcal{C}_A,\mathcal{C}_B)\) has distance at least \(\delta^2(\delta-\lambda)\).

Testability of the final code: The code \(\mathcal{C}(\mathcal{X}; \mathcal{C}_A,\mathcal{C}_B)\) comes equipped with a natural local tester: given a word \(w \in \{0,1\}^{\mathcal{S}}\), pick a random \(x \in \mathcal{V}(\mathcal{X})\) and check if \(w|_{\mathcal{X}_x} \in \mathcal{C}_A \otimes \mathcal{C}_B\). The key result of Dinur, Evra, Livne, Lubotzky, and Mozes (besides the above construction) is that there exist constants \(\lambda, \delta, \tau \in (0,1)\) such that if the Schreier graphs \(\mathop{\mathrm{Sch}}(X,G_L,A)\) and \(\mathop{\mathrm{Sch}}(X,G_R,B)\) are \(\lambda\)-expander graphs and the tensor-product code \(\mathcal{C}_A \otimes \mathcal{C}_B\) is \(\tau\)-robustly testable, then the above tester is a good local tester for \(\mathcal{C}(\mathcal{X}; \mathcal{C}_A,\mathcal{C}_B)\). The proof proceeds via a natural self-correction algorithm whose correctness is proved using elementary properties of the underlying expander graphs and robust testability of the tensor codes.

Instantiating the square complex with a family of left-right Cayley complexes with left and right generators \(A\) and \(B\) satisfies the “no-conjugacy condition,” and random LDPC codes whose tensor product is robustly testable yields the family of \(c^3\) locally testable codes.

This construction is yet another illustration of how high-dimensional expanders are useful in code constructions. Recent work due to Kaufman and Minzer [KM22] is yet another demonstration where the properties of the Grassmannian complex are used to yield an extremely elegant proof of the testability of the Reed-Muller code. We believe these results are just the tip of an iceberg and strongly hope that this interaction between high-dimensional expanders and error-correcting codes continues to be fruitful and yields several more fascinating results.

References

[BHR05]: Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova. Some 3CNF properties are hard to test. SIAM J. Comput., 35(1):1–21, 2005. (Preliminary version in 35th STOC, 2003). doi:10.1137/S0097539704445445.

[BLR93]: Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549–595, December 1993. (Preliminary version in 22nd STOC, 1990). doi:10.1016/0022-0000(93)90044-W.

[BS08]: Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM J. Comput., 38(2):551–607, 2008. (Preliminary version in 37th STOC, 2005). eccc:2004/TR04-060, doi:10.1137/050646445.

[BV09]: Eli Ben-Sasson and Michael Viderman. Tensor products of weakly smooth codes are robust. Theory Comput., 5(1):239–255, 2009. (Preliminary version in 12th RANDOM, 2008). eccc: 2009/TR09-007, doi:10.4086/toc.2009.v005a012.

[DDHR20]: Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Noga Ron-Zewi. Locally testable codes via high-dimensional expanders, 2020. (manuscript). arXiv:2005.01045, eccc:2020/ TR20-072.

[DELLM22]: Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. Locally testable codes with constant rate, distance, and locality. In Stefano Leonardi and Anupam Gupta, eds., Proc. \(54\)th ACM Symp. on Theory of Computing (STOC), pages 357–374. 2022. arXiv:2111.04808, eccc:2021/TR21-151, doi:10.1145/3519935.3520024.

[Din07]: Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. (Preliminary version in 38th STOC, 2006). eccc:2005/TR05-046, doi:10.1145/1236457.1236459.

[DSW06]: Irit Dinur, Madhu Sudan, and Avi Wigderson. Robust local testability of tensor products of LDPC codes. In Josep Dı́az, Klaus Jansen, José D. P. Rolim, and Uri Zwick, eds., Proc. \(10\)th International Workshop on Randomization and Computation (RANDOM), volume 4110 of LNCS, pages 304–315. Springer, 2006. eccc:2006/TR06-118, doi:10.1007/11830924\_29.

[Gol21]: Oded Goldreich. On the locally testable code of Dinur et al. (2021). Technical Report 2021/TR21-175, Elect. Colloq. on Comput. Complexity (ECCC), 2021. eccc:2021/TR21-175.

[KL14]: Tali Kaufman and Alexander Lubotzky. High dimensional expanders and property testing. In Moni Naor, ed., Proc. \(5\)th Innovations in Theor. Comput. Sci. (ITCS), pages 501–506. ACM, 2014. arXiv:1312.2367, doi:10.1145/2554797.2554842.

[KM22]: Tali Kaufman and Dor Minzer. Improved optimal testing results from global hypercontractivity. In Jelani Nelson, ed., Proc. \(63\)rd IEEE Symp. on Foundations of Comp. Science (FOCS). 2022. (To appear). arXiv:2202.08688.

[PK22]: Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical LDPC codes. In Stefano Leonardi and Anupam Gupta, eds., Proc. \(54\)th ACM Symp. on Theory of Computing (STOC), pages 375–388. 2022. arXiv:2111.03654, doi:10. 1145/3519935.3520017.

[Spi95]: Daniel A. Spielman. Computationally Efficient Error-Correcting Codes and Holographic Proofs. Ph.D. thesis, Massachusetts Institute of Technology, June 1995.

[SS96]: Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Trans. Inform. Theory, 42(6):1710–1722, November 1996. (Preliminary version in 35th FOCS, 1994). doi:10.1109/ 18.556667.

[Val05]: Paul Valiant. The tensor product of two codes is not necessarily robustly testable. In Chandra Chekuri, Klaus Jansen, José D. P. Rolim, and Luca Trevisan, eds., Proc. \(9\)th International Workshop on Randomization and Computation (RANDOM), volume 3624 of LNCS, pages 472–481. Springer, 2005. doi:10.1007/11538462\_40.

---

1. The formal definition of local testability is more involved; however, it reduces to this notion if we restrict our attention to linear codes [BHR05].↩︎

2. We will not define HDXs formally in this note; we will, however, define the complexes that yield the \(c^3\) LTCs in full detail later on.↩︎

3. The summer cluster on Error-Correcting Codes and High-Dimensional Expansion (July 11 to August 9, 2019) at the Simons Institute at UC Berkeley: https://simons.berkeley.edu/programs/ecc2019.↩︎