Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers

Kiran S. Kedlaya, Sergey Yekhanin

A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only…