The Taub Faculty of Computer Science Events and Talks

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. Over the past decade, 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. Joint work with Swastik Kopparty, Noga Ron-Zewi, and Shubhangi Saraf.