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.

Updated version

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.

updated version

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.