@InProceedings{RS82a, replaced-by = { RS82c }, author = { Ronald L. Rivest and Adi Shamir }, title = { How to reuse a ``write-once'' memory (Preliminary version) }, doi = { 10.1145/800070.802182 }, acmid = { 802182 }, pages = { 105--113 }, acm = { 09698 }, booktitle = { Proceedings of the fourteenth annual ACM symposium on Theory of Computing }, isbn = { 0-89791-070-2 }, publisher = { ACM }, date = { 1982-05 }, OPTyear = { 1982 }, OPTmonth = { May 5--7, }, OPTeditor = { Harry R. Lewis }, eventtitle = { STOC'82 }, eventdate = { 1982-05-05/1982-05-07 }, venue = { San Francisco, California }, abstract = { Storage media such as digital optical disks, PROMS, or paper tape consist of a number of ``write-once'' bit positions (wits); each wit initially contains a ``0'' that may later be irreversibly overwritten with a ``1''. We demonstrate that such ``write-once memories'' (woms) can be ``rewritten'' to a surprising degree. For example, only 3 wits suffice to represent any 2-bit value in a way that can be later update to represent any other 2-bit value. For large $k$, $1.29\ldots \cdot k$ wits suffice to represent a $k$-bit value in a way that can be similarly updated. Most surprising, allowing $t$ writes of a $k$-bit value requires only $t+o(t)$ wits, for any fixed $k$. For fixed $t$, approximately $k\cdot t/\log(t)$ wits are required as $k\rightarrow\infty$. An $n$-wite WOM is shown to have a ``capacity'' (i.e. $kt$ when writing a $k$-bit value $t$ times) of up to $n \log (n)$ bits. }, }