link

July 8, Wednesday
12:00 – 13:30

List-decoding Reed-Muller codes
Graduate seminar
Lecturer : Mr. Shachar Lovett
Lecturer homepage : sites.google.com/site/shacharlovetthomepage/
Affiliation : Weizmann Institute of Science
Location : 201/37
Host : Graduate Seminar
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.