February 25, Wednesday
12:00 – 14:00
On the efficiency of local decoding procedures for error-correcting codes
Graduate seminar
Lecturer : Michal Moshkovitz
Affiliation : Tel-Aviv University
Location : 201/37
Host : graduate seminar
Jonathan Katz and Luca Trevisan defined the concept of Locally Decodable Codes (LDC). LDC are error correcting codes where a bit of the message can be probabilistically recovered by looking at a limited number of symbols of a corrupted encoding.
After defining LDCs formally we will see some negative results. First, that local decoding is impossible when looking at only one symbol of the corrupted encoding. Then we will see a lower bound on the codewords' length.
This paper appeared in STOC00.