Improved list decodability of polynomial codes

Combinatorics Seminar
Event time: 
Thursday, April 18, 2019 - 4:00pm
DL 431
Swastik Kopparty
Speaker affiliation: 
Rutgers University
Event description: 

I will talk about a recent result showing that some well-studied polynomial-based error-correcting codes
(Folded Reed-Solomon Codes and Multiplicity Codes) are “list-decodable up to capacity with constant
list-size”.   At its core, this is a statement about questions of the form: “Given some points in the plane,
how many low degree univariate polynomials are such that their graphs pass through 10% of these points”?   This leads to list-decodable and locally list-decodable error-correcting codes with the best known parameters. 

Based on joint work with Noga Ron-Zewi, Shubhangi Saraf and Mary Wootters.

Research Area(s):