A large alphabet Locally Decodable Code (LDC) $C:\Sigma^{k} \to \Sigma'^{n}$, where $\Sigma'$ may be large, is a code where each symbol of $x$ can be decoded by making few queries to a noisy version of $C(x)$. The rate of $C$ is its information rate, namely $\frac{k \log (|\Sigma|) }{n \log ... more >>>

In a breakthrough in the long-going attempt to construct good explicit tree codes, Cohen, Haeupler and Schulman (CHS) (STOC 2018) constructed constant-distance tree codes with rate 1/O(log log n). In their construction a large-alphabet tree code is used as a core element - and they were able to utilize polynomials ... more >>>

A $q$-locally correctable code (LCC) $C:\{0,1\}^k \to \{0,1\}^n$ is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most $q$ queries to the word. The cases in which $q$ is constant are of special interest, and so are the ... more >>>