Locally Decodable Codes

Klim Efremenko
Tel-Aviv University; Member, School of Mathematics
September 27, 2012


A code C is said to be Locally Decodable Code with q queries if it is possible to recover any symbol x_j of a message x by making at most q queries to C(x), such that even if a constant fraction of C(x) is corrupted, the decoding algorithm returns the correct answer with high probability.