אריאל גביזון (מדעי המחשב, טכניון)
יום רביעי, 1.5.2013, 12:30
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.