Computer Science Speaker Series Master Calendar

View Full Calendar

Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets

Event Type
Seminar/Symposium
Sponsor
Computer Science
Location
Thomas M. Siebel Center for Computer Science 201 North Goodwin Avenue, Urbana, IL 61801, Room# 3401
Date
Apr 22, 2024   11:00 am  
Speaker
Zeyu Guo (Ohio State University)
Contact
Michael A Forbes
E-Mail
miforbes@illinois.edu
Phone
217-300-0454
Views
23
Originating Calendar
Computer Science Speakers Calendar

This paper shows that, with high probability, randomly punctured Reed-Solomon codes over fields of polynomial size achieve the list decoding capacity. More specifically, we prove that for any ϵ>0 and R∈(0,1), with high probability, randomly punctured Reed-Solomon codes of block length n and rate R are (1−R−ϵ,O(1/ϵ)) list decodable over alphabets of size at least 2^{poly(1/ϵ)}n^2. This extends the recent breakthrough of Brakensiek, Gopi, and Makam (STOC 2023) that randomly punctured Reed-Solomon codes over fields of exponential size attain the generalized Singleton bound of Shangguan and Tamo (STOC 2020).

 

       Joint work with Zihan Zhang.  FOCS 23.  arxiv.org/abs/2304.01403 .

link for robots only