The Taub Faculty of Computer Science Events and Talks

Kuznetsov and Tsybakov considered the problem of storing information in a memory where a certain p-fraction of the n cells are `stuck' at certain values. The person writing in the memory - the `encoder'- knows which cells are stuck, and to what values. The person who will read the memory later - the `decoder' is required to retrieve the message encoded without the information about which cells are stuck. Kuznetsov and Tsybakov showed there are schemes where a message of length (1− p − o(1)) • n can be encoded. We give the rst such explicit schemes.

Our schemes follow from a construction of an object called an `invertible zero-error disperser'.

Joint work with Ronen Shaltiel.