Computer Science – Information Theory
Scientific paper
2008-11-26
Computer Science
Information Theory
32 pages
Scientific paper
We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. We show that for {\em every} code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). This gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. We show that for {\em every} code, its list decoding radius remains unchanged under $m$-wise interleaving for an integer $m$. This generalizes a recent result of Dinur et al \cite{DGKS}, who proved such a result for interleaved Hadamard codes (equivalently, linear transformations). Using the notion of generalized Hamming weights, we give better list size bounds for {\em both} tensoring and interleaving of binary linear codes. By analyzing the weight distribution of these codes, we reduce the task of bounding the list size to bounding the number of close-by low-rank codewords. For decoding linear transformations, using rank-reduction together with other ideas, we obtain list size bounds that are tight over small fields.
Gopalan Parikshit
Guruswami Venkatesan
Raghavendra Prasad
No associations
LandOfFree
List Decoding Tensor Products and Interleaved 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 Tensor Products and Interleaved Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and List Decoding Tensor Products and Interleaved Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-275053