@unpublished{ref:CCS25,
  author =	 {Yeyuan Chen and Mahdi Cheraghchi and Nikhil Shagrithaya},
  title =	 {Optimal Erasure Codes and Codes on Graphs},
  year =	 2025,
  url_Paper =	 {https://arxiv.org/abs/2504.03090},
  note = {Preprint arXiv:2504.03090},
  abstract =	 {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.}
}

{"_id":"Zk8rHGS77GgDX4bw7","bibbaseid":"chen-cheraghchi-shagrithaya-optimalerasurecodesandcodesongraphs-2025","author_short":["Chen, Y.","Cheraghchi, M.","Shagrithaya, N."],"bibdata":{"bibtype":"unpublished","type":"unpublished","author":[{"firstnames":["Yeyuan"],"propositions":[],"lastnames":["Chen"],"suffixes":[]},{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["Nikhil"],"propositions":[],"lastnames":["Shagrithaya"],"suffixes":[]}],"title":"Optimal Erasure Codes and Codes on Graphs","year":"2025","url_paper":"https://arxiv.org/abs/2504.03090","note":"Preprint arXiv:2504.03090","abstract":"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.","bibtex":"@unpublished{ref:CCS25,\n author =\t {Yeyuan Chen and Mahdi Cheraghchi and Nikhil Shagrithaya},\n title =\t {Optimal Erasure Codes and Codes on Graphs},\n year =\t 2025,\n url_Paper =\t {https://arxiv.org/abs/2504.03090},\n note = {Preprint arXiv:2504.03090},\n abstract =\t {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:\n \n1. 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;\n\n2. 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;\n\n3. A strongly explicit construction of erasure codes on non-bipartite graphs (more generally, linear codes on symmetric square matrices) achieving improved rates;\n\n4. A strongly explicit construction of linear nearly-MDS codes over constant-sized alphabets that can be encoded and decoded in quasi-linear time.}\n}\n\n","author_short":["Chen, Y.","Cheraghchi, M.","Shagrithaya, N."],"key":"ref:CCS25","id":"ref:CCS25","bibbaseid":"chen-cheraghchi-shagrithaya-optimalerasurecodesandcodesongraphs-2025","role":"author","urls":{" paper":"https://arxiv.org/abs/2504.03090"},"metadata":{"authorlinks":{}},"downloads":3},"bibtype":"unpublished","biburl":"http://mahdi.ch/writings/cheraghchi.bib","dataSources":["YZqdBBx6FeYmvQE6D"],"keywords":[],"search_terms":["optimal","erasure","codes","codes","graphs","chen","cheraghchi","shagrithaya"],"title":"Optimal Erasure Codes and Codes on Graphs","year":2025,"downloads":6}