Theory Seminar: Invertible Zero-Error Dispersers and Defective Memory with Stucks-At Errors

Ariel Gabizon (CS, Technion) - CANCELLED
Wednesday, 1.5.2013, 12:30
Taub 201

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.

Back to the index of events