Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 06, 2021, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Saeed Ilchi
A code over alphabet Σ and with block length n is (ρ,L)-list decodable if any hamming ball of radius ρn in Σn contains at most L codewords. We are interested in maximum ρ where the code is (ρ,L=poly(n))-list decodable.
For Reed-Solomon codes with arbitrary evaluation points, we cannot expect a rate significantly better than ε2 to list decode up to radius 1-ε. This indeed matches the Johnson bound. Although, it has shown that if we take an RS-code with random evaluation points, the rate becomes Õ(ε). Moreover, the list size is constant, say O(1/ε). We will discuss this result based on the works of Shangguan, and Tamo (https://arxiv.org/abs/1911.01502), and Guo, Li, Shangguan, Tamo, and Wootters (https://arxiv.org/abs/2011.04453).
Automatic MiSe System Software Version 1.4803M | admin login