Showing 2024Show all
3 papers · 1 filter
cs.IT2024
Polynomials, Divided Differences, and Codes
S. Venkitesh
Multivariate multiplicity codes (Kopparty, Saraf, and Yekhanin, J. ACM 2014) are linear codes where the codewords are described by evaluations of multivariate polynomials (with a d…
cs.IT2024
Random Reed-Solomon Codes are List Recoverable with Optimal List Size
Dean Doron, S. Venkitesh
We prove that Reed-Solomon (RS) codes with random evaluation points are list recoverable up to capacity with optimal output list size, for any input list size. Namely, given an inp…
cs.IT2024
Efficient List-decoding of Polynomial Ideal Codes with Optimal List Size
Noga Ron-Zewi, S. Venkitesh, Mary Wootters
In a recent breakthrough [BGM23, GZ23, AGL23], it was shown that randomly punctured Reed-Solomon codes are list decodable with optimal list size with high probability, i.e., they a…