Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

Understand

We prove that a random linear code over F_q, with probability arbitrarily close to 1, is list decodable at radius (1-1/q-\epsilon) with list size L=O(1/\epsilon^2) and rate R=\Omega_q(\epsilon^2/(log^3(1/\epsilon))).

• Up to the polylogarithmic factor in (1/\epsilon) and constant factors depending on q, this matches the lower bound L=\Omega_q(1/\epsilon^2) for the list size and upper bound R=O_q(\epsilon^2) for the rate.
• Previously only existence (and not abundance) of such codes was known for the special case q=2 (Guruswami, H{\aa}stad, Sudan and Zuckerman, 2002).
• In order to obtain our result, we employ a relaxed version of the well known Johnson bound on list decoding that translates the average Hamming distance between codewords to list decoding guarantees.