It has been known since [Zyablov and Pinsker 1982] that a random q-ary code of rate 1-H_q(\rho)-\eps (where 0<\rho<1-1/q, \eps>0 and H_q(\cdot) is the q-ary entropy function) with high probability is a (\rho,1/\eps)-list decodable code. (That is, every Hamming ball of radius at most \rho n has at most 1/\eps ... more >>>

We prove that a random linear code over \mathbb{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 ... more >>>