We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding n-variate degree-d polynomials over {\mathbb F}_q with q \ge \Omega(d/\delta), we present an explicit (multi)-set S \subseteq {\mathbb F}_q^n of size N=\mathrm{poly}(n^d/\delta) such that every nonzero polynomial vanishes on at most ... more >>>

We construct two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction 1-R-\epsilon of adversarial errors where R is the rate of the code, for any desired positive constant \epsilon. The alphabet size depends only on \epsilon and is nearly-optimal.

The ... more >>>