Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Mersenne numbers:
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 >>>

TR10-173 | 9th November 2010
Yeow Meng Chee, Tao Feng, San Ling, Huaxiong Wang, Liang Feng Zhang

Query-Efficient Locally Decodable Codes

A $k$-query locally decodable code (LDC)
$\textbf{C}:\Sigma^{n}\rightarrow \Gamma^{N}$ encodes each message $x$ into
a codeword $\textbf{C}(x)$ such that each symbol of $x$ can be probabilistically
recovered by querying only $k$ coordinates of $\textbf{C}(x)$, even after a
constant fraction of the coordinates have been corrupted.
Yekhanin (2008)
constructed a $3$-query LDC ... more >>>

ISSN 1433-8092 | Imprint