Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Kiran Kedlaya:

TR07-040 | 12th April 2007
Kiran Kedlaya, Sergey Yekhanin

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

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 k bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. The major ... more >>>

ISSN 1433-8092 | Imprint