Weight Distribution and List-Decoding size of Reed-Muller codes
by
Tulasi Mohan Molli(STCS, TIFR)
→
Asia/Kolkata
A-201 STCS Seminar Room
A-201 STCS Seminar Room
Description
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].
