ECCC-Report TR23-126https://eccc.weizmann.ac.il/report/2023/126Comments and Revisions published for TR23-126en-usFri, 25 Aug 2023 16:45:27 +0300
Paper TR23-126
| AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets |
Omar Alrabiah,
Venkatesan Guruswami,
Ray Li
https://eccc.weizmann.ac.il/report/2023/126A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate $R$ codes are not list-decodable using list-size $L$ beyond an error fraction $\frac{L}{L+1} (1-R)$ (the Singleton bound being the case of $L=1$, i.e., unique decoding). We prove that in order to approach this bound for any fixed $L >1$, one needs exponential alphabets. Specifically, for every $L>1$ and $R\in(0,1)$, if a rate $R$ code can be list-of-$L$ decoded up to error fraction $\frac{L}{L+1} (1-R -\varepsilon)$, then its alphabet must have size at least $\exp(\Omega_{L,R}(1/\varepsilon))$. This is in sharp contrast to the situation for unique decoding where certain families of rate $R$ algebraic-geometry (AG) codes over an alphabet of size $O(1/\varepsilon^2)$ are unique-decodable up to error fraction $(1-R-\varepsilon)/2$.
Our lower bound is tight up to constant factors in the exponent: with high probability random codes (or, as shown recently, even random linear codes) over $\exp(O_L(1/\varepsilon))$-sized alphabets, can be list-of-$L$ decoded up to error fraction $\frac{L}{L+1} (1-R -\varepsilon)$. Fri, 25 Aug 2023 16:45:27 +0300https://eccc.weizmann.ac.il/report/2023/126