2012/09/05 by Amir Shpilka, Shpilka, Amir · 1 citation
Computer Science · Engineering · Mathematics · #Cellular Automata and Applications #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.CC #cs.IT #graph theory and CDMA systems #math.IT
paper · pdf · doi:10.48550/arxiv.1209.1128
14 pages
arxiv created 2012/09/05 · openalex publication_date 2012/09/05 · arxiv updated 2012/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we give an explicit construction of a capacity achieving family of binary t-write WOM codes for any number of writes t, that have a polynomial time encoding and decoding algorithms. The block length of our construction is N=(t/ε)O(t/(δε)) when εis the gap to capacity and encoding and decoding run in time N1+δ. This is the first deterministic construction achieving these parameters. Our techniques also apply to larger alphabets.