|
Seminar Announcement Date: Tuesday, 7 January 2025 Time: 03:30 PM Venue: LH3 Fast list-decoding of univariate multiplicity and Folded Reed-Solomon codes Rohan Goyal Massachusetts Institute of Technology, USA. 07-01-25 Abstract We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon codes can be made to run in O~(n) time. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list decoding. It is known that for every ϵ>0, and rate r∈(0,1), there exist explicit families of these codes that have rate r and can be list decoded from a (1−r−ϵ) fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above list-decoding tasks in O~(n), where n is the block-length of the code. Our algorithms have two main components. The first component builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a O~(n) time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design O~(n) time algorithms for two natural algebraic problems: given a (m+2)-variate polynomial Q(x,y0,…,ym)=Q~(x)+∑mi=0Qi(x)⋅yi the first algorithm solves order-m linear differential equations of the form Q(x,f(x),dfdx,…,dmfdxm)≡0 while the second solves functional equations of the form Q(x,f(x),f(γx),…,f(γmx))≡0, where m is an arbitrary constant and γ is a field element of sufficiently high order. These algorithms can be viewed as generalizations of classical O~(n) time algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest. Based on joint work with Prahladh Harsha, Mrinal Kumar, and Ashutosh Shankar.
|
