List decoding of noisy Reed-Muller-like codes
<|reference_start|>List decoding of noisy Reed-Muller-like codes: 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.<|reference_end|>
@article{calderbank2006list,
    title={List decoding of noisy Reed-Muller-like codes},
    author={A. R. Calderbank, Anna C. Gilbert, and Martin J. Strauss},
    journal={arXiv preprint arXiv:cs/0607098},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0607098},
    primaryClass={cs.DS cs.IT math.IT}
}