For every fixed finite field F_q, p between 0 and 1-1/q, and positive epsilon, we prove that with high probability a random subspace C of F_q^n of dimension (1-h_q(p)-epsilon)n has the property that every Hamming ball of radius pn has at most O(1/epsilon) elements of C. (Here h_q(x) is the q-ary entropy function.)

This answers a basic open question concerning the list-decodability of linear codes, showing that a list size of O(1/epsilon) suffices to have rate within epsilon of the "list decoding capacity" 1-h_q(p). This matches up to constant factors the list-size achieved by general (non-linear) random codes, and gives an exponential improvement over the best previously known list-size bound of q^{O(1/epsilon)}.

The main technical ingredient in our proof is a strong upper bound on the probability that m random vectors chosen from a Hamming ball centered at the origin have too many (more than O(m)) vectors from their linear span also belong to the ball.

The talk will be self-contained and not assume any coding theory background.

Joint work with Johan Hastad and Swastik Kopparty.