Tutorial: Locally decodable codes

Friday, February 17, 2012 - 9:00am - 10:00am
Keller 3-180
Anna Gal (The University of Texas at Austin)
Tutorial: Locally decodable codes

Locally decodable codes are error correcting codes with the extra property that, in order to retrieve the correct value of any one position of the input with
high probability, it is sufficient to read a small number of positions of the corresponding, possibly corrupted codeword. In applications involving large data sets it is desirable to have decoding procedures that work in sublinear time, that is, without having to access all of the encoded data. Locally decodable codes allow very efficient decoding procedures for recovering individual parts of the original data: not only with sublinear, but sometimes even small constant running times. I will survey constructions of locally decodable codes and the currently known tradeoffs between parameters of such codes.