标题： 最优擦除码与图上的码 显示英文标题

标题： Optimal Erasure Codes and Codes on Graphs

摘要： 我们构造了固定字母表上具有常数规模的线性纠错码集合，这些集合可以纠正给定比例的对抗性擦除，并且其速率可以任意接近Singleton界。 我们给出了结果的几个应用： 1. 在任何固定字母表上显式构建强线性种子符号修复提取器和无损压缩器，仅需常数长度的种子，并具有最优的输出长度； 2. 在二分图上的擦除码的强显式构造（更一般地，在任意维度矩阵上的线性码），具有最优的速率和擦除修正折中； 3. 在非二分图上的擦除码的强显式构造（更一般地，在对称平方矩阵上的线性码），实现了改进的速率； 4. 在固定大小字母表上具有准线性时间编码和解码能力的线性近似MDS码的强显式构造。 显示英文摘要

摘要： 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.