Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Explicit Constructions of WOM Codes
event speaker icon
Amir Shpilka (CS Technion)
event date icon
Wednesday, 08.01.2014, 12:30
event location icon
Taub 201
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.