Computer Science/Discrete Mathematics Seminar II

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.