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 >>>

Reed-Solomon (RS) codes were recently shown to exhibit an intriguing $\textit{proximity gap}$ phenomenon. Specifically, given a collection of strings with some algebraic structure (such as belonging to a line or affine space), either all of them are $\delta$-close to RS codewords, or most of them are $\delta$-far from the code. ... more >>>

All known proofs of the PCP theorem rely on multiple "composition" steps, where PCPs over large alphabets are turned into PCPs over much smaller alphabets at a (relatively) small price in the soundness error of the PCP. Algebraic proofs, starting with the work of Arora, Lund, Motwani, Sudan, and Szegedy ... more >>>