2025/04/03 by Yeyuan Chen, Chen, Yeyuan, Mahdi Cheraghchi +3 · 1 voice · 2 citations
Computer Science · #Coding theory and cryptography #Cooperative Communication and Network Coding #Error Correcting Code Techniques #cs.DM #cs.IT #math.CO
paper · pdf · doi:10.48550/arxiv.2504.03090
openalex publication_date 2025/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We construct constant-sized ensembles of linear error-correcting codes over any fixed alphabet that can correct a given fraction of adversarial erasures at rates approaching the Singleton bound arbitrarily closely. We provide several applications of our results: 1. Explicit constructions of strong linear seeded symbol-fixing extractors and lossless condensers, over any fixed alphabet, with only a constant seed length and optimal output lengths; 2. A strongly explicit construction of erasure codes on bipartite graphs (more generally, linear codes on matrices of arbitrary dimensions) with optimal rate and erasure-correction trade-offs; 3. A strongly explicit construction of erasure codes on non-bipartite graphs (more generally, linear codes on symmetric square matrices) achieving improved rates; 4. A strongly explicit construction of linear nearly-MDS codes over constant-sized alphabets that can be encoded and decoded in quasi-linear time.