List decoding of noisy Reed-Muller-like codes
| dc.creator | Calderbank, A. R. | |
| dc.creator | Gilbert, Anna C. | |
| dc.creator | Strauss, Martin J. | |
| dc.date | 2006-07-20 | |
| dc.date | 2006-08-02 | |
| dc.date.accessioned | 2026-07-07T08:18:01Z | |
| dc.date.available | 2026-07-07T08:18:01Z | |
| dc.description | First- and second-order Reed-Muller (RM(1) and RM(2), respectively) codes are two fundamental error-correcting codes which arise in communication as well as in probabilistically-checkable proofs and learning. In this paper, we take the first steps toward extending the quick randomized decoding tools of RM(1) into the realm of quadratic binary and, equivalently, Z_4 codes. Our main algorithmic result is an extension of the RM(1) techniques from Goldreich-Levin and Kushilevitz-Mansour algorithms to the Hankel code, a code between RM(1) and RM(2). That is, given signal s of length N, we find a list that is a superset of all Hankel codewords phi with dot product to s at least (1/sqrt(k)) times the norm of s, in time polynomial in k and log(N). We also give a new and simple formulation of a known Kerdock code as a subcode of the Hankel code. As a corollary, we can list-decode Kerdock, too. Also, we get a quick algorithm for finding a sparse Kerdock approximation. That is, for k small compared with 1/sqrt{N} and for epsilon > 0, we find, in time polynomial in (k log(N)/epsilon), a k-Kerdock-term approximation s~ to s with Euclidean error at most the factor (1+epsilon+O(k^2/sqrt{N})) times that of the best such approximation. | |
| dc.identifier | https://arxiv.org/abs/cs/0607098 | |
| dc.identifier | http://arxiv.org/abs/cs/0607098 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134288 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Information Theory | |
| dc.subject | E.4; F.2.1 | |
| dc.title | List decoding of noisy Reed-Muller-like codes | |
| dc.type | text |