Weight distribution and List-Decoding size of Reed-Muller codes

Details: We will finish the remainder of previous student talk. We will begin where we ended last time.

Abstract of the previous talk: The problem of list-decoding an error-correcting code is the following:
given a received word and a distance parameter find all codewords of the code that are within the given distance from the received word. It is a generalization of the more common notion of unique decoding.

The weight distribution of an error-correcting code counts, for every given weight parameter, the number of codewords whose hamming weight is less than the given weight parameter.

The codewords of Reed-Muller code can be thought of as truth-tables of low degree polynomials. Kaufman, Lovett, and Porat in their work from 2010 made a novel connection between computer science techniques used for studying low-degree polynomials and these seemingly related coding theory questions in the case of Reed-Muller codes.

In this talk, we will see

1) The above-mentioned result of Kaufman, Lovett, and Porat[KLP10] and subsequent improvement of it due to Abbe, Sphilka, and Wigderson[ASW15] which give upper bounds on the weight distribution of Reed-Muller codes.

2) A lower bound on the weight-distribution of Reed-Muller codes by exhibiting a collection of low-degree polynomials that satisfy the weight requirement for any given weight parameter. This is joint work with Bhandari, Harsha, and Saptarishi and independently discovered by Sberlo and Shpilka[SS20].