The Taub Faculty of Computer Science Events and Talks

A write-once-memory is a type of memory in which cells can only be written once. I.e. we can write “1” to a cell that currently has the value “0”, but not the other way around. It is not hard to show that if one wishes to use the memory to store t messages (i.e. write to the memory t times), then the total number of information bits that can be stored is at most log(t+1)*n, when n is the number of memory cells. It is a challenging task to obtain encoding schemes that achieve this capacity bound, and that have reasonable block-length (i.e. not too large n).

In this talk we shall present 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, and whose block length is exponential in (eps/t), where eps is the gap to capacity.

The talk is self contained and no background on WOM codes is assumed.