Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

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

The List-Decoding Size of Reed-Muller Codes

Revision #2
Authors: Tali Kaufman, Shachar Lovett, Ely Porat
Accepted on: 22nd September 2014 23:12
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
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