List-decoding of Reed-Solomon Codes and variants �in �near-linear time

Prahladh Harsha

​

​

​

Based on joint works with Rohan Goyal (MIT), Mrinal Kumar, Ashutosh Shankar (TIFR)

Noisy polynomial and Hermite interpolation�in �near-linear time

Prahladh Harsha

​

​

​

Based on joint works with Rohan Goyal (MIT), Mrinal Kumar, Ashutosh Shankar (TIFR)

Reed-Solomon code

Noisy Polynomial Interpolation

List-decoding

List-decoding

List-decoding problem

Noisy Polynomial Interpolation

List-recovery problem

Noisy Polynomial Interpolation

Reed-Solomon code and friends

Noisy Hermite Interpolation

List-decoding univariate multiplicity

History of Algorithmic List-Decoding of Polynomial Codes

• [Sudan ’96] list-decoding for RS codes beyond unique-decoding radius
• [Guruswami-Sudan ‘98] list-decoding of RS codes up to Johnson radius
• [Alekhnovich ‘02] Near linear-time version of GS algorithm
• [Parvaresh-Vardy ’05] list-decoding beyond Johnson radius
• [Guruswami-Rudra ‘06] list-decoding of FRS codes up to capacity
• [Kopparty ‘13 and Guruswami-Wang ‘13] multiplicity codes up to capacity
• [Kopparty-RonZewi-Saraf-Wootters ‘18] constant-sized lists for FRS and mult codes
• [Goyal-H-Kumar-Shankar ‘24] Near linear time version of GW list-decoding algorithm
• [Srivastava ‘25 and Chen-Zhang ‘25] Optimal list-size for list-decoding FRS & mult codes
• [Goyal-H-Kumar-Shankar ‘25] Near linear time version of GW list-recovery algorithm
• [Ashvinkumar-Habib-Srivastava ‘25] Algorithmic version of [S’25]

​

​

​

Fast list-decoding and list-recovery

• [Sudan ’96] list-decoding for RS codes beyond unique-decoding radius
• [Guruswami-Sudan ‘98] list-decoding of RS codes up to Johnson radius
• [Alekhnovich ‘02] Near linear-time version of GS algorithm
• [Parvaresh-Vardy ’05] list-decoding beyond Johnson radius
• [Guruswami-Rudra ‘06] list-decoding of FRS codes up to capacity
• [Kopparty ‘13 and Guruswami-Wang ‘13] multiplicity codes up to capacity
• [Kopparty-RonZewi-Saraf-Wootters ‘18] constant-sized lists for FRS and mult codes
• [Goyal-H-Kumar-Shankar ‘24] Near linear time version of GW list-decoding algorithm
• [Srivastava ‘25 and Chen-Zhang ‘25] Optimal list-size for list-decoding FRS & mult codes
• [Goyal-H-Kumar-Shankar ‘25] Near linear time version of GW list-recovery algorithm
• [Ashvinkumar-Habib-Srivastava ‘25] Algorithmic version of [S’25]

​

​

​

Fast list-decoding

Near-linear time algorithms

a la Alekhnovich

Sudan’s algorithm (RS list decoding)

Guruswami-Sudan algorithm (RS list decoding)

Alekhnovich’s speedup

Extending to multiplicity codes

Guruswami-Wang algorithm (UM list decoding)

This is efficient and decodes up to capacity but not nearly-linear time.

Speedup of Interpolation Step

Finding low-degree solution in linear system:

• GW algorithm: Linear system presented as system of linear equations
• [a la Alekhnovich] Linear system presented via a set of generating polynomials as a lattice
• Use Minkowski theorem to find shortest vector in the lattice

​

​

​

Speedup of Interpolation Step

Speedup of ODE Solver

Solving the simple case

Solving the simple case

Two smaller problems of the same type. Recurse!

• Problem: Solutions are no longer unique and we cannot afford to branch
• Solution:
• We only need to obtain a basis of the affine space of solutions
• For each basis vector, construct a proxy differential equation with a unique solution
• A version of divide-and-conquer works there

Summarizing ..

Open Questions?

• Generalization to multivariate polynomials?

​

• Extensions to Kopparty’s decoding algorithm?
• Linear ODE vs non-linear ODE

​

• Better understanding of standard RS decoding beyond the Johnson radius?

​

​

​

Thank You