Combinatorics Seminar
When: Sunday, May 3, 10am
Where: Schreiber 309
Speaker: Shachar Lovett, Weizmann
Title:
List-decoding for Reed-Muller Codes
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. We provide asymptotic bounds
for the list-decoding size of Reed-Muller codes that apply to all
distances. Previous results of Gopalan, Klivans and Zuckerman apply
to
distances only up to the minimum distance of the code.
Additionally, we study the weight distribution of Reed-Muller
codes.
We provide bounds for the weight distribution of Reed-Muller codes
that
apply to all distances. Previous results by Azumi, Kasami and
Tokura
apply to distances only up to 2.5 times the minimum distance
of the code.
Joint work with Tali Kaufman.