Here is a list of codes related to locally decodable codes.
| Code | Description |
|---|---|
| Batch code | Binary code designed for minimizing the total amount of storage and the worst-case maximal load on any device in a distributed system. |
| Expander code | LDPC code whose parity-check matrix is derived from the adjacency matrix of a bipartite expander graph [1] such as a Ramanujan graph or a Cayley graph of a projective special linear group over a finite field [2,3]. Expander codes admit efficient encoding and decoding algorithms and yield an explicit (i.e., non-random) asymptotically good LDPC code family. |
| 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 a received 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 received word (assuming the received 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 a received 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 received word (assuming the received 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\). |
| Private information retrieval (PIR) code | A code used to obtain information from several servers privately, i.e., without the servers knowing what information was obtained. |
| Quantum locally recoverable code (QLRC) | A QLRC of locality \(r\) is a block quantum code whose code states can be recovered after a single erasure by accessing at most \(r-1\) other subsystems and applying a recovery map. |
| \(q\)-ary linear LCC | A \(q\)-ary linear code for which one can recover any coordinate of a codeword from at most \(r\) coordinates of a received word (assuming the corruption rate is within some tolerated threshold \(\delta\)). |
References
- [1]
- S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
- [2]
- A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
- [3]
- G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI