Speaker:Dr. Chong Shangguan is a postdoc at the Department of EE – Systems of Tel Aviv University, Israel. He graduated from Zhejiang University in 2017 with a Ph.D. degree. He is mainly engaged in the interdisciplinary research of combinatorial mathematics and information science, and has published more than 10 SCI papers.
Date:June 05, 2020
Time:15:00-16:00
Location: Welcome to ZOOM meeting, https://zoom.com.cn/j/2936654514
Abstract:
List-decoding of Reed-Solomon (RS) codes beyond the so called Johnson radius has been one of the main open questions in coding theory since the work of Guruswami and Sudan. It is now known by the work of Rudra and Wootters, using techniques from high dimensional probability, that over large enough alphabets there exist RS codes that are list-decodable beyond this radius.
In this talk, we take a more combinatorial approach which allows us to determine the precise relation (up to the exact constant) between the decoding radius and the list size. We prove a generalized Singleton bound for a given list size, and show that the bound is tight for list size $L=2$. As a by-product we show that most RS codes with a rate of at least $1/4$ are list-decodable beyond the Johnson radius. We also give the first explicit construction of such RS codes.
The main tool used in the proof is the polynomial method that captures a new type of linear dependency between codewords of a code that are contained in a small Hamming ball.
Inviter:Prof. Sihuang Hu
Edited by:Xu Zeyu
