Tata Institute of Fundamental Research
List decoding and Higher Order MDS codes
STCS Seminar
Speaker:
Manik Dhar (Massachusetts Institute of Technology)
Organiser:
Mrinal Kumar
Date:
Tuesday, 18 Jun 2024, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
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.
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 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 any Reed-Solomon codes achieve any generic zero pattern this implies that they generically achieve list decoding capacity.
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.
Short Bio:
Manik Dhar is an Instructor (Postdoc) of Applied Mathematics at Massachusetts Institute of Technology. He received his BTech at the Indian Institute of Technology - Bombay in 2016, MS at Stanford University in 2018, and received his PhD from Princeton in 2023 where he was advised by Zeev Dvir. He is broadly interested in discrete mathematics and theoretical computer science.
| Speaker: | Manik Dhar (Massachusetts Institute of Technology) |
| Organiser: | Mrinal Kumar |
| Date: | Tuesday, 18 Jun 2024, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
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.
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 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 any Reed-Solomon codes achieve any generic zero pattern this implies that they generically achieve list decoding capacity.
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.
Short Bio:
Manik Dhar is an Instructor (Postdoc) of Applied Mathematics at Massachusetts Institute of Technology. He received his BTech at the Indian Institute of Technology - Bombay in 2016, MS at Stanford University in 2018, and received his PhD from Princeton in 2023 where he was advised by Zeev Dvir. He is broadly interested in discrete mathematics and theoretical computer science.