Here is a list of codes related to locally testable codes.
| Code | Description |
|---|---|
| Balanced code | An even-length-\(n\) \(q\)-ary code whose nonzero codewords all have a Hamming weight of \(n/2\). A code is \(\epsilon\)-balanced if the relative weight (i.e., weight divided by \(n\)) of all nonzero codewords lies in the interval \([\frac{1-\epsilon}{2},\frac{1+\epsilon}{2}]\). A code is \(\gamma\)-unbiased if the relative weight lies in the interval \((\frac{1}{2}-\frac{1}{n^{\gamma}},\frac{1}{2}+\frac{1}{n^{\gamma}})\). |
| Ben-Sasson-Goldreich-Harsha-Sudan-Vadhan (BGHSV) code | Locally testable \([n,k,d]\) code with \(n = k^{1+\epsilon}\) and query complexity of order \(O(1/\epsilon)\) for any \(\epsilon > 0\). |
| Ben-Sasson-Sudan code | Locally testable \([n,k/2,d]_{2^m}\) code with \(k\) a power of two, \(n = k \log^{c} k\), and query complexity \(\log^{c}k\) for some universal constant \(c\). |
| Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code | Locally testable \([n,k,d]\) code with \(n = k \cdot 2^{\tilde{O}(\sqrt{\log k})}\) and asymptotically constant query complexity, where \(\tilde{O}(f)=O(f\cdot (\log f)^c)\) for some fixed constant \(c\). |
| Binary linear LTC | A binary linear code \(C\) of length \(n\) that is a \((u,R)\)-LTC with query complexity \(u\) and soundness \(R>0\). |
| Bose–Chaudhuri–Hocquenghem (BCH) code | Cyclic \(q\)-ary code, with \(n\) and \(q\) relatively prime, whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\). More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=q^r-1\) for some \(r\geq 2\). More general BCH codes can be defined for zeroes are powers of the form \(\{b,b+s,b+2s,\cdots,b+(\delta-2)s\}\) where gcd\((s,n)=1\). |
| Cyclic linear \(q\)-ary code | A \(q\)-ary code of length \(n\) is cyclic if, for each codeword \(c_1 c_2 \cdots c_n\), the cyclically shifted string \(c_n c_1 \cdots c_{n-1}\) is also a codeword. A cyclic code is called primitive when \(n=q^r-1\) for some \(r\geq 2\). A shortened cyclic code is obtained from a cyclic code by taking only codewords with the first \(j\) zero entries, and deleting those zeroes. |
| Cyclic linear binary code | A binary code of length \(n\) is cyclic if, for each codeword \(c_1 c_2 \cdots c_n\), the cyclically shifted string \(c_n c_1 \cdots c_{n-1}\) is also a codeword. A cyclic code is called primitive when \(n=2^r-1\) for some \(r\geq 2\). A shortened cyclic code is obtained from a cyclic code by taking only codewords with the first \(j\) zero entries, and deleting those zeroes. |
| Dinur code | Member of infinite family of locally testable \([n,n/\text{polylog}(n),d]\) codes with vanishing rate. Code construction relies on a construction utilizing tensor-product codes [1]. |
| Expander LP code | Family of \(G\)-lifted product codes constructed using two random classical Tanner codes defined on expander graphs [2]. For certain parameters, this construction yields the first asymptotically good QLDPC codes. Classical codes resulting from this construction are one of the first two families of \(c^3\)-LTCs. |
| Galois-qudit expander code | Galois-qudit CSS code constructed from a hypergraph product of expander codes. |
| Generalized RM (GRM) code | Reed-Muller code GRM\(_q(r,m)\) of length \(n=q^m\) over \(GF(q)\) with \(0\leq r\leq m(q-1)\). Its codewords are evaluations of the set of all degree-\(\leq r\) polynomials in \(m\) variables at the points of \(GF(q)\). |
| Goldreich-Sudan code | Locally testable \([n,k,d]\) code with \(n = k^{1+O(1/u)}\) and distance of order \(\Omega(n)\) for query complexity \(u\). The same work also presented a probabilistic construction of codes of size \(k^{1+o(1)}\). |
| Goppa code | Let \( G(x) \) be a polynomial describing a projective-plane curve with coefficients from \( GF(q^m) \) for some fixed integer \(m\). Let \( L \) be a finite subset of the extension field \( GF(q^m) \) where \(q\) is prime, meaning \( L = \{\alpha_1, \cdots, \alpha_n\} \) is a subset of nonzero elements of \( GF(q^m) \). A Goppa code \( \Gamma(L,G) \) is an \([n,k,d]_q\) linear code consisting of all vectors \(a = a_1, \cdots, a_n\) such that \( R_a(x) =0 \) modulo \(G(x)\), where \( R_a(x) = \sum_{i=1}^n \frac{a_i}{z - \alpha_i} \). |
| Hadamard code | An \([2^m,m,2^{m-1}]\) balanced binary code. The \([2^m,m+1,2^{m-1}]\) augmented Hadamard code is the first-order RM code (a.k.a. RM\((1,m)\)), while the \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)). |
| Hypergraph product (HGP) code | A member of a family of CSS codes whose stabilizer generator matrix is obtained from a hypergraph product of two classical linear binary codes. Codes from hypergraph products in higher dimension are called higher-dimensional HGP codes [3]. |
| Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code | Member of a family of locally testable binary linear codes with constant rate, constant relative distance, and subpolynomial query complexity \(u = (\log n)^{O(\log \log n)}\)). Later work by Gopi, Kopparty, Oliveira, Ron-Zewi, and Saraf [4] showed that related concatenated codes achieve the GV bound. |
| Left-right Cayley complex code | Binary code constructed on a left-right Cayley complex using a pair of base codes \(C_A,C_B\) and an expander graph [2] such that codewords for a fixed graph vertex are codewords of the tensor code \(C_A \otimes C_B\). A family of such codes is one of the first \(c^3\)-LTCs. |
| Linear binary code | An \((n,2^k,d)\) linear code is denoted as \([n,k]\) or \([n,k,d]\), where \(d\) is the code's distance. Its codewords form a linear subspace, i.e., for any codewords \(x,y\), \(x+y\) is also a codeword. A code that is not linear is called nonlinear. |
| Locally correctable code (LCC) | Recall that a block code encodes a length-\(k\) message into a length-\(n\) codeword, which is then sent through a noise channel to yield an error word. Informally, an LCC is a block code for which one can recover any coordinate of a codeword from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)). |
| Locally decodable code (LDC) | Recall that a block code encodes a length-\(k\) message into a length-\(n\) codeword, which is then sent through a noise channel to yield an error word. Informally, an LDC is a block code for which one can recover any coordinate of the message from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)). Efficiency of the correction is quantified by the code's query complexity \(r\), and correction is performed by sampling subsets of \(r\) bits. |
| Locally testable code (LTC) | Code for which one can efficiently check whether a given string is a codeword or is far from a codeword. Efficiency of the verification is quantified by the code's query complexity \(u\), while effectiveness is quantified by the code's soundness \(R\). |
| Long code | Locally testable \([2^{2^k},k,d]\) code. The encoder maps a \(k\)-bit string into a codeword that consists of the values of all Boolean functions on the \(k\)-bit string. The code is not practical, but is useful for certain probabilistically checkable proof (PCP) constructions [5]. |
| Lossless expander balanced-product code | QLDPC code constructed by taking the balanced product of lossless expander graphs. Using one part of a quantum-code chain complex constructed with one-sided loss expanders [6] yields a \(c^3\)-LTC [7]. Using two-sided expanders, which are only conjectured to exist, yields an asymptotically good QLDPC code family [8]. |
| Meir code | Locally testable \([n,k,d]_q\) code with query complexity \(\text{poly}(\log k)\) and rejection ratio \(R/n = 1/\text{poly}(\log k)\). Code construction is probabilistic and combinatorial. |
| Multiplicity code | A generalization of an \(m\)-variate polynomial evaluation code based on evaluating polynomials and \(s\) of their derivatives at all points in \(GF(q)^m\). Originally proposed for coding using the Rosenbloom-Tsfasman metric [9]. Univariate (\(m=1\)) [9,10] and multivariante (\(m>1\)) [11] codes have been proposed. |
| Quantum locally testable code (QLTC) | A local commuting-projector Hamiltonian-based block quantum code which has a nonzero average-energy penalty for creating large errors. Informally, QLTC error states that are far away from the codespace have to be excited states by a number of the code's local projectors that scales linearly with \(n\). |
| Reed-Muller (RM) code | Member of the RM\((r,m)\) family of linear binary codes derived from multivariate polynomials. The code parameters are \([2^m,\sum_{j=0}^{r} {m \choose j},2^{m-r}]\), where \(r\) is the order of the code satisfying \(0\leq r\leq m\). First-order RM codes are also called biorthogonal codes, while \(m\)th order RM codes are also called universe codes. Punctured RM codes RM\(^*(r,m)\) are obtained from RM codes by deleting one coordinate from each codeword. |
| Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). |
| Tanner code | A linear \(q\)-ary code defined on a bipartite graph similar to a Tanner graph. This generalized Tanner graph consists of variable nodes and constraint nodes, with the generalization being that the constraint nodes of degree \(r\) now represent a linear codes of length \(r\). |
| \(q\)-ary linear LTC | A \(q\)-ary linear code \(C\) of length \(n\) that is a \((u,R)\)-LTC with query complexity \(u\) and soundness \(R>0\). More technically, the code is a \((u,R)\)-LTC if the rows of its parity-check matrix \(H\in GF(q)^{r\times n}\) have weight at most \(u\) and if \begin{align} \frac{1}{r}|H x| \geq \frac{R}{n} D(x,C) \tag*{(1)}\end{align} holds for any \(q\)-ary string \(x\), where \(D(x,C)\) is the \(q\)-ary Hamming distance between \(x\) and the closest codeword to \(x\) [12; Def. 11]. A code satisfying the above constraint without the weight-\(u\) restriction is called an \(R\)-testable code [13]. |
References
- [1]
- E. Ben-Sasson and M. Sudan, “Robust Locally Testable Codes and Products of Codes”, (2004) arXiv:cs/0408066
- [2]
- S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
- [3]
- W. Zeng and L. P. Pryadko, “Higher-Dimensional Quantum Hypergraph-Product Codes with Finite Rates”, Physical Review Letters 122, (2019) arXiv:1810.01519 DOI
- [4]
- S. Gopi et al., “Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound”, IEEE Transactions on Information Theory 64, 5813 (2018) DOI
- [5]
- P. Harsha et al., “Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)”, (2010) arXiv:1002.3864
- [6]
- M. Capalbo et al., “Randomness conductors and constant-degree lossless expanders”, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (2002) DOI
- [7]
- T.-C. Lin and M.-H. Hsieh, “\(c^3\)-Locally Testable Codes from Lossless Expanders”, (2022) arXiv:2201.11369
- [8]
- T.-C. Lin and M.-H. Hsieh, “Good quantum LDPC codes with linear time decoder from lossless expanders”, (2022) arXiv:2203.03581
- [9]
- M. Yu. Rosenbloom, M. A. Tsfasman, “Codes for the m-Metric”, Probl. Peredachi Inf., 33:1 (1997), 55–63; Problems Inform. Transmission, 33:1 (1997), 45–52
- [10]
- Rasmus R. Nielsen. List decoding of linear block codes. PhD thesis, Technical University of Denmark, 2001
- [11]
- S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI
- [12]
- A. Leverrier, V. Londe, and G. Zémor, “Towards local testability for quantum coding”, Quantum 6, 661 (2022) arXiv:1911.03069 DOI
- [13]
- M. Chapman, T. Vidick, and H. Yuen, “Efficiently stable presentations from error-correcting codes”, (2023) arXiv:2311.04681