Language - Chinese



Current location: HOME > EVENTS & ANNOUCEMENTS > Content

Combinatorial list-decoding of Reed-Solomon codes

Date: 2020-06-04    Hits:    Source:

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,


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.

Source:School of Cyber Science and Technology

Edited by: Liu Fang

72 Bihai Road, Jimo, Qingdao, P.R. China

Copyright @Shandong University LuICPFile 05001952