FR4.R3.1

Points-Polynomials Incidence Theorem with an Application to Reed-Solomon Codes

Itzhak Tamo, Tel-Aviv University, Israel

Session:
List Decoding

Track:
1: Algebraic Aspects of Coding Theory

Location:
Ypsilon IV-V-VI

Presentation Time:
Fri, 12 Jul, 16:25 - 16:45

Session Chair:
Vinayak Ramkumar, Tel Aviv University
Abstract
This paper focuses on incidences over finite fields, extending to higher degrees a result by Vinh \cite{VINH20111177} on the number of point-line incidences in the plane $\mathbb{F}^2$, where $\mathbb{F}$ is a finite field. Specifically, we present a bound on the number of incidences between points and polynomials of bounded degree in $\mathbb{F}^2$. Our approach employs a singular value decomposition of the incidence matrix between points and polynomials, coupled with an analysis of the related group algebras. This bound is then applied to coding theory, specifically to the problem of average-radius list decoding of Reed-Solomon (RS) codes. We demonstrate that RS codes of certain lengths are average-radius list-decodable with a constant list size, which is dependent on the code rate and the distance from the Johnson radius. While a constant list size for list-decoding of RS codes in this regime was previously established, its existence for the stronger notion of average-radius list-decoding was not known to exist.
Resources