Tata Institute of Fundamental Research
Linear-algebraic List Decoding and Subspace-evasive Sets
Seminar
Speaker:
Venkatesan Guruswami (Carnegie Mellon University
Computer Science Department
Gates-Hillman Complex 7211
5000 Forbes Avenue
Pittsburgh, PA 15213
United States of America)
Organiser:
Jaikumar Radhakrishnan
Date:
Tuesday, 31 Jul 2012, 16:00 to 17:00
Venue:
AG-66
(Scan to add to calendar)
Abstract:
We will describe a simple linear-algebraic approach to list decode Reed-Solomon codes with evaluation points from a subfield. The algorithm is able to correct an error fraction approaching the information-theoretically maximum limit of $1-R$ where $R$ is the rate of the code.
The algorithm can be thought of as a higher-dimensional version of the Welch-Berlekamp decoder, and pins down the candidate solutions to a subspace of non-trivially smaller dimension. By pre-coding the messages to belong to a pseudorandomly constructed "subspace-evasive set" that has small intersection with subspaces of the sort output by the decoder, one can prune the subspace to a small list of close-by codewords in polynomial time.
This approach to list decoding is quite versatile, and applies to variants of Reed-Solomon codes (the context where it was first discovered), folded algebraic-geometric codes (which yields efficiently list-decodable codes with simultaneously near-optimal rate, list size, and alphabet size), and Gabidulin codes (the rank-metric analog of Reed-Solomon codes). Time permitting, we might briefly touch upon some of these variants.
Based on joint work with Chaoping Xing.
| Speaker: | Venkatesan Guruswami (Carnegie Mellon University Computer Science Department Gates-Hillman Complex 7211 5000 Forbes Avenue Pittsburgh, PA 15213 United States of America) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Tuesday, 31 Jul 2012, 16:00 to 17:00 |
| Venue: | AG-66 |
(Scan to add to calendar)
Abstract:
We will describe a simple linear-algebraic approach to list decode Reed-Solomon codes with evaluation points from a subfield. The algorithm is able to correct an error fraction approaching the information-theoretically maximum limit of $1-R$ where $R$ is the rate of the code.
The algorithm can be thought of as a higher-dimensional version of the Welch-Berlekamp decoder, and pins down the candidate solutions to a subspace of non-trivially smaller dimension. By pre-coding the messages to belong to a pseudorandomly constructed "subspace-evasive set" that has small intersection with subspaces of the sort output by the decoder, one can prune the subspace to a small list of close-by codewords in polynomial time.
This approach to list decoding is quite versatile, and applies to variants of Reed-Solomon codes (the context where it was first discovered), folded algebraic-geometric codes (which yields efficiently list-decodable codes with simultaneously near-optimal rate, list size, and alphabet size), and Gabidulin codes (the rank-metric analog of Reed-Solomon codes). Time permitting, we might briefly touch upon some of these variants.
Based on joint work with Chaoping Xing.
The algorithm can be thought of as a higher-dimensional version of the Welch-Berlekamp decoder, and pins down the candidate solutions to a subspace of non-trivially smaller dimension. By pre-coding the messages to belong to a pseudorandomly constructed "subspace-evasive set" that has small intersection with subspaces of the sort output by the decoder, one can prune the subspace to a small list of close-by codewords in polynomial time.
This approach to list decoding is quite versatile, and applies to variants of Reed-Solomon codes (the context where it was first discovered), folded algebraic-geometric codes (which yields efficiently list-decodable codes with simultaneously near-optimal rate, list size, and alphabet size), and Gabidulin codes (the rank-metric analog of Reed-Solomon codes). Time permitting, we might briefly touch upon some of these variants.
Based on joint work with Chaoping Xing.