BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1419
DTSTAMP:20240603T043420Z
SUMMARY:List decoding and Higher Order MDS codes
DESCRIPTION:Speaker: Manik Dhar (Massachusetts Institute of Technology)\n\n
Abstract: \nA [n\,k] code C is a k-dimensional subspace in F_q^n. C is sai
d to be MDS (maximal distance separable) if its hamming weight is n-k+1 wh
ich 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. T
his can be rewritten as saying that any two subspaces formed by the column
s of the generator matrix of C intersect as minimally as possible.\nBraken
siek\, Gopi\, and Makam generalize this notion to introduce MDS(l) codes w
here we ask that any l subspace formed by the columns of the generator mat
rix of C intersect as minimally as possible. In a series of works\, they s
how their new notion is equivalent to an alternative notion of higher-orde
r MDS codes introduced by Roth related to list decoding. In particular\, t
he parity check matrix of code being MDS(l) is equivalent to having (avera
ge-case) combinatorial list decoding guarantees. They also show that being
MDS(l) is equivalent to the generator matrix being able to achieve generi
c 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.\nGuo-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 l
inear by an improved argument due to Alrabiah\, Guruswami\, and Li). This
talk will cover these exciting developments and recent works by the speake
r with Brakensiek\, Gopi\, and Zhang which develop this theory over codes
sampled from irreducible varieties\, prove a GM-MDS theorem for this setti
ng\, and prove that punctured AG codes are list decodable up to capacity o
ver constant size fields.\n \nShort Bio:\nManik Dhar is an Instructor (Po
stdoc) 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 di
screte mathematics and theoretical computer science.\n
URL:https://www.tcs.tifr.res.in/web/events/1419
DTSTART;TZID=Asia/Kolkata:20240618T160000
DTEND;TZID=Asia/Kolkata:20240618T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR