ARC-TRIAD Colloquium
Mary Wootters
Monday, October 1, 2018
MiRC Pettit 102A&B - 11:00 am
Title: Improved Decoding of Folded Reed-Solomon and Multiplicity Codes
Abstract: List-decoding is an important primitive in the theory of error correcting codes, and it has long been a goal to obtain explicit constructions of capacity-achieving, efficiently list-decodable codes. Folded Reed-Solomon Codes (Guruswami-Rudra 2008) and Multiplicity codes (Guruswami-Wang 2011, Kopparty 2012) are two such constructions. However, previous analysis of these codes could not guarantee optimal parameters. In particular, the “list-size” of these codes was only shown to be polynomial, while ideally it would be constant. Thus, over the past decade or so, there have been several modifications of these codes aimed at reducing the list size to constant. In this work, we show that in fact the list-sizes were constant all along, with no modifications required! Further, we use our result for univariate multiplicity codes to establish improved local list-decoding results for multivariate multiplicity codes.
In this talk, I’ll define all the terms in the paragraph above (in particular, no prior knowledge of error correcting codes is necessary!), and sketch the proofs of the results mentioned above.
Joint work with Swastik Kopparty, Noga Ron-Zewi, and Shubhangi Saraf.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
