Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Private Information Retrival:
TR11-154 | 17th November 2011
Klim Efremenko

From Irreducible Representations to Locally Decodable Codes

Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially

In this paper we ... more >>>

TR16-189 | 21st November 2016
Arnab Bhattacharyya, Sivakanth Gopi

Lower bounds for 2-query LCCs over large alphabet

A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates.
We show that any zero-error $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to \Sigma^n$ that can correct a constant fraction of corrupted symbols must ... more >>>

ISSN 1433-8092 | Imprint