Improved decoding of folded reed-solomon and multiplicity codes

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions of codes known to achieve list-decoding capacity; multivariate multiplicity codes were the first constructions of high-rate locally correctable codes; and univariate multiplicity codes are also known to achieve list-decoding capacity. However, previous analyses of the error-correction properties of these codes did not yield optimal results. In particular, in the list-decoding setting, the guarantees on the list-sizes were polynomial in the block length, rather than constant; and for multivariate multiplicity codes, local list-decoding algorithms could not go beyond the Johnson bound. In this paper, we show that Folded Reed-Solomon codes and multiplicity codes are in fact better than previously known in the context of list-decoding and local list-decoding. More precisely, we first show that Folded RS codes achieve listdecoding capacity with constant list sizes, independent of the block length; and that high-rate univariate multiplicity codes can also be list-recovered with constant list sizes. Using our result on univariate multiplicity codes, we show that multivariate multiplicity codes are high-rate, locally list-recoverable codes. Finally, we show how to combine the above results with standard tools to obtain capacity achieving locally list decodable codes with query complexity significantly lower than was known before.

Original languageEnglish (US)
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
PublisherIEEE Computer Society
Pages212-223
Number of pages12
ISBN (Electronic)9781538642306
DOIs
StatePublished - Nov 30 2018
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: Oct 7 2018Oct 9 2018

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2018-October

Other

Other59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
CountryFrance
CityParis
Period10/7/1810/9/18

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Folded Reed-Solomon codes
  • List decodable codes
  • Locally decodable codes
  • Multiplicity code

Fingerprint Dive into the research topics of 'Improved decoding of folded reed-solomon and multiplicity codes'. Together they form a unique fingerprint.

Cite this