|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Improved List-Decoding and Local List-Decoding Algorithms for Polynomial Codes|
|Affiliation:||Rutgers University; Member, School of Mathematics|
|Date:||Tuesday, March 5|
|Time/Room:||10:30am - 12:30pm/West Building Lecture Hall|
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 upto 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.