Capacity-Achieving Multiwrite WOM Codes

In this paper, we give an explicit construction of a family of capacity-achieving binary t-write WOM codes for any number of writes t, which have 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 N^1+δ. This is the first deterministic construction achieving these parameters. Our techniques also apply to larger alphabets.