Seminars

View all Seminars  |  Download ICal for this event

List decoding and Higher Order MDS codes

Series: Bangalore Theory Seminars

Speaker: Manik Dhar MIT

Date/Time: Jun 07 11:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
A [n,k] code C is a k-dimensional subspace in F_q ^n. C is said to be MDS (maximal distance separable) if its hamming weight is n-k+1 which is the largest possible by the singleton bound. It is also equivalent to saying that every k minor of the generator matrix of C is invertible. This can be rewritten as saying that any two subspaces formed by the columns of the generator matrix of C intersect as minimally as possible.
<br>
Brakensiek, Gopi, and Makam generalize this notion to introduce MDS(l) codes where we ask that any l subspace formed by the columns of the generator matrix of C intersect as minimally as possible. In a series of works, they show their new notion is equivalent to an alternative notion of higher-order MDS codes introduced by Roth related to list decoding. In particular, the parity check matrix of a code being MDS(l) is equivalent to having (average-case) combinatorial list decoding guarantees. They also show that being MDS(l) is equivalent to the generator matrix being able to achieve generic zero patterns. Using the GM-MDS theorem which says that generic Reed-Solomon codes achieve any generic zero pattern this implies that they generically achieve list decoding capacity.
<br>
Guo-Zhang proved punctured Reed-Solomon codes can achieve list decoding capacity over quadratic in n size fields by introducing a slack to these notions (this was later strengthened to linear by an improved argument due to Alrabiah, Guruswami, and Li). This talk will cover these exciting developments and recent works by the speaker with Brakensiek, Gopi, and Zhang which develop this theory over codes sampled from irreducible varieties, prove a GM-MDS theorem for this setting, and prove that punctured AG codes are list decodable up to capacity over constant size fields.
<br>
<br>
Microsoft teams link:
<br>
Link
<br>
We are grateful to the Kirani family for generously supporting the theory seminar series
<br>
<br>
Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar