BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/294
DTSTAMP:20230914T125918Z
SUMMARY:Linear-algebraic List Decoding and Subspace-evasive Sets
DESCRIPTION:Speaker: Venkatesan Guruswami (Carnegie Mellon University\nComp
 uter Science Department\nGates-Hillman Complex 7211\n5000 Forbes Avenue\nP
 ittsburgh\, PA 15213\nUnited States of America)\n\nAbstract: \nWe will des
 cribe a simple linear-algebraic approach to list decode Reed-Solomon codes
  with evaluation points from a subfield. The algorithm is able to correct 
 an error fraction approaching the information-theoretically maximum limit 
 of $1-R$ where $R$ is the rate of the code.\nThe algorithm can be thought 
 of as a higher-dimensional version of the Welch-Berlekamp decoder\, and p
 ins down the candidate solutions to a subspace of non-trivially smaller di
 mension. By pre-coding the messages to belong to a pseudorandomly construc
 ted "subspace-evasive set" that has small intersection with subspaces of t
 he sort output by the decoder\, one can prune the subspace to a small list
  of close-by codewords in polynomial time.\nThis approach to list decoding
  is quite versatile\, and applies to variants of Reed-Solomon codes (the c
 ontext where it was first discovered)\, folded algebraic-geometric codes (
 which yields efficiently list-decodable codes with simultaneously near-opt
 imal rate\, list size\, and alphabet size)\, and Gabidulin codes (the rank
 -metric analog of Reed-Solomon codes). Time permitting\, we might briefly 
 touch upon some of these variants.\nBased on joint work with Chaoping Xing
 .\n
URL:https://www.tcs.tifr.res.in/web/events/294
DTSTART;TZID=Asia/Kolkata:20120731T160000
DTEND;TZID=Asia/Kolkata:20120731T170000
LOCATION:AG-66
END:VEVENT
END:VCALENDAR