Locally Decodable Codes with Randomized Encoding

Understand

We initiate a study of locally decodable codes with randomized encoding.

• Standard locally decodable codes are error correcting codes with a deterministic encoding function and a randomized decoding function, such that any desired message bit can be recovered with good probability by querying only a small number of positions in the corrupted codeword.
• This allows one to recover any message bit very efficiently in sub-linear or even logarithmic time.
• Besides this straightforward application, locally decodable codes have also found many other applications such as private information retrieval, secure multiparty computation, and average-case complexity.