Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR08-111 | 22nd September 2014 23:12

The List-Decoding Size of Reed-Muller Codes

RSS-Feed




Revision #2
Authors: Tali Kaufman, Shachar Lovett, Ely Porat
Accepted on: 22nd September 2014 23:12
Downloads: 2915
Keywords: 


Abstract:

The weight distribution and list-decoding size of Reed-Muller codes are studied in this work. Given a weight parameter, we are interested in bounding the number of Reed-Muller codewords with weight up to the given parameter; and given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word.

Obtaining tight bounds for the weight distribution of Reed-Muller codes has been a long standing open problem in coding theory, dating back to 1976. In this work, we make a new connection between computer science techniques used to study low-degree polynomials and these coding theory questions. This allows us to resolve the weight distribution and list-decoding size of Reed-Muller codes for all distances. Previous results could only handle bounded distances: Azumi,Kasami and Tokura gave bounds on the weight distribution which hold up to $2.5$ times the minimal distance of the code; and Gopalan, Klivans and Zuckerman gave bounds on the list-decoding size which hold up to the Johnson bound.



Changes to previous version:

Updated version


Revision #1 to TR08-111 | 18th February 2012 04:28

The List-Decoding Size of Reed-Muller Codes





Revision #1
Authors: Tali Kaufman, Shachar Lovett, Ely Porat
Accepted on: 18th February 2012 04:28
Downloads: 3479
Keywords: 


Abstract:

The weight distribution and list-decoding size of Reed-Muller
codes are studied in this work. Given a weight parameter, we are
interested in bounding the number of Reed-Muller codewords with a
weight of up to the given parameter. Additionally, given a
received word and a distance parameter, we are interested in
bounding the size of the list of Reed-Muller codewords that are
within that distance from the received word. In this work, we make
a new connection between computer science techniques used for
studying low-degree polynomials and these coding theory questions.
Using this connection we progress significantly towards resolving
both the weight distribution and the list-decoding problems.

Obtaining tight bounds for the weight distribution of Reed-Muller
codes has been a long standing open problem in coding theory,
dating back to 1976 and seemingly resistent to the common coding
theory tools. The best results to date are by Azumi, Kasami and
Tokura which provide bounds on the weight distribution that apply
only up to $2.5$ times the minimal distance of the code. We
provide asymptotically tight bounds for the weight distribution of
the Reed-Muller code that apply to {\em all} distances.

List-decoding has both theoretical and practical applications in
various fields. To name a few, hardness amplification in
complexity, constructing hard-core predicates from one way
functions in cryptography and learning parities with noise in
learning theory.

Many algorithms for list-decoding have the crux of their analysis
lying in bounding the list-decoding size. The case for
Reed--Muller codes is similar, and Gopalan, Klivans and Zuckerman
gave a list-decoding algorithm, whose complexity is determined by
the list-decoding size. Gopalan et.~al provided bounds on the
list-decoding size of Reed--Muller codes which apply only up to
the minimal distance of the code. We provide asymptotically tight
bounds for the list-decoding size of Reed--Muller codes which
apply to {\em all} distances.



Changes to previous version:

updated version


Paper:

TR08-111 | 14th November 2008 00:00

The List-Decoding Size of Reed-Muller Codes





TR08-111
Authors: Shachar Lovett, Tali Kaufman
Publication: 24th December 2008 15:41
Downloads: 3354
Keywords: 


Abstract:

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman~\cite{GKZ08} on the list size of Reed-Muller codes apply only up to the minimum distance of the code. In this work we provide asymptotic bounds for the list-decoding size of Reed-Muller codes that apply for {\em all} distances. Additionally, we study the weight distribution of Reed-Muller codes. Prior results of Kasami and Tokura~\cite{KT70} on the structure of Reed-Muller codewords up to twice the minimum distance, imply bounds on the weight distribution of the code that apply only until twice the minimum distance. We provide accumulative bounds for the weight distribution of Reed-Muller codes that apply to {\em all} distances.



ISSN 1433-8092 | Imprint