2024/08/28 by Yeyuan Chen, Zihan Zhang, Chen, Yeyuan +1 · 1 voice · 9 citations
Computer Science · #Coding theory and cryptography #Quantum-Dot Cellular Automata #Cooperative Communication and Network Coding
paper · pdf · doi:10.48550/arxiv.2408.15925
In this paper, we prove that explicit FRS codes and multiplicity codes achieve relaxed generalized Singleton bounds for list size L≥1. Specifically, we show the following: (1) FRS code of length n and rate R over the alphabet \mathbbFqs with distinct evaluation points is ((L)/(L+1)(1-(sR)/(s-L+1)),L) list-decodable (LD) for list size L∈[s]. (2) Multiplicity code of length n and rate R over the alphabet \mathbbFps with distinct evaluation points is ((L)/(L+1)(1-(sR)/(s-L+1)),L) LD for list size L∈[s]. Choosing s=Θ(1/ε2) and L=O(1/ε), our results imply that both FRS codes and multiplicity codes achieve LD capacity 1-R-ε with optimal list size O(1/ε). This exponentially improves the previous state of the art (1/ε)O(1/ε) established by Kopparty et. al. (FOCS 2018) and Tamo (IEEE TIT, 2024). In particular, our results on FRS codes fully resolve a open problem proposed by Guruswami and Rudra (STOC 2006). Furthermore, our results imply the first explicit constructions of (1-R-ε,O(1/ε)) LD codes of rate R with poly-sized alphabets. Our method can also be extended to analyze the list-recoverability (LR) of FRS codes. We provide a tighter radius upper bound that FRS codes cannot be ((L+1-ℓ)/(L+1)(1-(mR)/(m-1))+o(1),ℓ, L) LR where m=\lceillogℓ(L+1)\rceil. We conjecture this bound is almost tight when L+1=ℓa for any a∈ℕ≥ 2. To give some evidences, we show FRS codes are ((1)/(2)-(sR)/(s-2),2,3) LR, which proves the tightness in the smallest non-trivial case. Our bound refutes the possibility that FRS codes could achieve LR capacity (1-R-ε, ℓ, O(\fracℓε)). This implies an intrinsic separation between LD and LR of FRS codes.