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...
| المؤلفون الرئيسيون: | , , |
|---|---|
| مؤلفون آخرون: | |
| التنسيق: | مقال |
| اللغة: | en_US |
| منشور في: |
Society for Industrial and Applied Mathematics
2014
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/1721.1/86093 |