Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
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 facto...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86093 |