Title: List-decoding of noisy Reed-Muller-like codes
Speaker: Anna Gilbert, University of Michigan
Date: Wednesday, November 8, 2006 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Coding theory has played a central role in the development of computer science. One critical point of interaction is decoding error-correcting 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, the first steps are taken toward extending the quick randomized decoding tools of RM(1) into the realm of quadratic binary and, equivalently, quaternary codes. The 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 of length N, a list is found that is a superset of all Hankel codewords with significant dot product in time poly(k,log(N)). A new and simple formulation of a known Kerdock code is given as a subcode of the Hankel code which leads to two immediate corollaries. First, the new Hankel list-decoding algorithm covers subcodes, including the new Kerdock construction, so it can list-decode Kerdock, too. Furthermore, because dot products of distinct Kerdock vectors have small magnitude, a quick algorithm is obtained for finding a sparse Kerdock approximation.
This is joint work with Robert Calderbank and Martin Strauss.