List decoding product and interleaved codes
Speaker: Venkatesan Guruswami , University of Washington
Date: April 7 2009
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Piotr Indyk, CSAIL, MIT
Contact: be, 3-6098, imbe@mit.edu
Relevant URL: >
> The list decoding problem consists of finding the list of all
> codewords that differ from an input string (the received word) in at
> most a certain fraction of positions (equal to the target
> error-correction radius). Informally, the list decoding radius of a
> code (family) is the largest error-correction radius for which the
> number of close-by codewords is polynomially bounded. Determining the
> list decoding radius of codes (and giving an efficient algorithm to
> decode up to this radius) is a challenging problem and remains open
> even for well studied codes such as Reed-Solomon codes.
>
> In this work, we give general list decoding algorithms for a broad
> class of codes. We design the first efficient algorithms and prove
> new combinatorial bounds for list decoding tensor products of codes
> and interleaved codes, and pin down the behavior of the list decoding
> radius under these basic operations. Our results yield rather general
> families of codes list decodable beyond the so-called Johnson radius.
>
> - We show that for every code, the ratio of its list decoding
> radius to its minimum distance stays unchanged under the tensor
> product operation. This gives new results on list decoding codes
> based on multivariate polynomials where the degree in each
> variable is bounded.
>
> - We show that for every code, its list decoding radius remains
> unchanged under arbitrary order interleaving. This generalizes a
> similar recent result for interleaved Hadamard codes
> (equivalently, decoding linear transformations).
>
> - Using the notion of generalized Hamming weights, we give better
> list size bounds for both tensoring and interleaving of binary
> linear codes. For decoding linear transformations, our list
> size bounds are tight over small fields.
>
> Joint work with Parikshit Gopalan and Prasad Raghavendra.
See other events that are part of Theory Colloquium 2008/2009
See other events happening in April 2009
