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 >>>

TR23-136 | 14th September 2023
Benny Applebaum, Oded Nir

Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography

A major open problem in information-theoretic cryptography is to obtain a super-polynomial lower bound for the communication complexity of basic cryptographic tasks. This question is wide open even for very powerful non-interactive primitives such as private information retrieval (or locally-decodable codes), general secret sharing schemes, conditional disclosure of secrets, and ... more >>>

ISSN 1433-8092 | Imprint