Alexander Barg

This is a research-expository paper. It deals with

complexity issues in the theory of linear block codes. The main

emphasis is on the theoretical performance limits of the

best known codes. Therefore, the main subject of the paper are

families of asymptotically good codes, i.e., codes whose rate and

relative ...
more >>>

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>>

Dean Doron, Jonathan Mosheiff, Mary Wootters

The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $\varepsilon^2$ has relative distance at least $\frac{1}{2} - O(\varepsilon)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters.

One hope to ... more >>>