List decodability of random linear codes

Venkatesan Guruswami, Carnegie Mellon University, Pittsburgh

For every fixed finite field F_q, 0 < p < 1-1/q, and epsilon > 0, 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.