Computer Science – Data Structures and Algorithms
Scientific paper
2006-07-20
Computer Science
Data Structures and Algorithms
Scientific paper
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.
Calderbank Robert A.
Gilbert Anna C.
Strauss Martin J.
No associations
LandOfFree
List decoding of noisy Reed-Muller-like codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with List decoding of noisy Reed-Muller-like codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and List decoding of noisy Reed-Muller-like codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-169016