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

DOI10.1137/1.9781611973105.31zbMath1440.94105OpenAlexW2952014918MaRDI QIDQ5741739

Mahdi Cheraghchi, Ameya Velingker, Venkatesan Guruswami

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973105.31

Mathematics Subject Classification ID

Gaussian processes (60G15) Linear codes (general theory) (94B05) Bounds on codes (94B65) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Probabilistic methods in Banach space theory (46B09) Decoding (94B35) Sampling theory in information and communication theory (94A20) Combinatorial aspects of packing and covering (05B40)

Related Items (5)

Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius ⋮ Polynomial approximation via compressed sensing of high-dimensional functions on lower sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Low-Density Parity-Check Codes Achieve List-Decoding Capacity

This page was built for publication: Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes