We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>

In this paper, we give surprisingly efficient algorithms for list-decoding and testing {\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable in the {\em high-error} regime with only a {\em constant} number of queries. More precisely, we show that for ... more >>>

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon > 0$, we prove that with high probability a random subspace $C$ of $\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the property that every Hamming ball of radius $pn$ has at most $O(1/\varepsilon)$ codewords. This answers a basic open question concerning ... more >>>