BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1719
DTSTAMP:20260514T053025Z
SUMMARY:Deterministic list decoding of Reed-Solomon codes
DESCRIPTION:Speaker: Soham Chatterjee (TIFR)\n\nAbstract: \nWe show that Re
 ed-Solomon codes of dimension $k$ and block length $n$ over any finite fie
 ld $\\mathbb{F}$ can be deterministically list decoded from agreement $\\s
 qrt{(k-1)n}$ in time $\\text{poly}(n\, \\log |\\mathbb{F}|)$.\nPrior to th
 is work\, the list decoding algorithms for Reed-Solomon codes\, from the c
 elebrated results of Sudan and Guruswami-Sudan\, were either randomized wi
 th time complexity $\\text{poly}(n\, \\log |\\mathbb{F}|)$ or were determi
 nistic with time complexity depending polynomially on the characteristic o
 f the underlying field. In particular\, over a prime field $\\mathbb{F}$\,
  no deterministic algorithms running in time $\\text{poly}(n\, \\log |\\ma
 thbb{F}|)$ were known for this problem.\n \nOur main technical ingredient
  is a deterministic algorithm for solving the bivariate polynomial factori
 zation instances that appear in the algorithm of Sudan and Guruswami-Sudan
  with only a $\\text{poly}(\\log |\\mathbb{F}|)$ dependence on the field s
 ize in its time complexity for every finite field $\\mathbb{F}$. While the
  question of obtaining efficient deterministic algorithms for polynomial f
 actorization over finite fields is a fundamental open problem even for uni
 variate polynomials of degree $2$\, we show that additional information fr
 om the received word can be used to obtain such an algorithm for instances
  that appear in the course of list decoding Reed-Solomon codes.\n \nRefer
 ence: https://arxiv.org/abs/2511.05176\n \n(To appear in STOC 2026)\n
URL:https://www.tcs.tifr.res.in/web/events/1719
DTSTART;TZID=Asia/Kolkata:20260515T160000
DTEND;TZID=Asia/Kolkata:20260515T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR