On locally decodable codes, self-correctable codes, and \(t\)-private PIR

DOI10.1007/S00453-008-9272-1zbMath1200.94055OpenAlexW2126982151MaRDI QIDQ603915

Enav Weinreb, Omer Barkol, Yuval Ishai

Publication date: 8 November 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9272-1

zbMATH Keywords

combinatorial designsHamada's conjecturelocally decodable codesprivate information retrieval\(t\)-PrivacyReed Muller codesself correctable codes

Mathematics Subject Classification ID

Burst-correcting codes (94B20)

Related Items (2)

Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin. ⋮ On Sums of Locally Testable Affine Invariant Properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its applications to error correcting codes
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• The geometric structure and the p-rank of an affine triple system derived from a nonassociative Moufang loop with the maximum associative center
• Designs and codes: An update
• Linear perfect codes and a characterization of the classical designs
• Minimum weight and dimension formulas for some geometric codes
• Player simulation and general adversary structures in perfect multiparty computation
• General constructions for information-theoretic private information retrieval
• Minimum-weight codewords as generators of generalized Reed-Muller codes
• Improved upper bounds on information-theoretic private information retrieval (extended abstract)
• How to share a secret
• Proof verification and the hardness of approximation problems
• On the efficiency of local decoding procedures for error-correcting codes
• A Geometric Approach to Information-Theoretic Private Information Retrieval
• Extractors
• Probabilistic checking of proofs
• Designing programs that check their work
• Interactive proofs and the hardness of approximating cliques
• Upper bound on the communication complexity of private information retrieval
• Advances in Cryptology - EUROCRYPT 2004
• Some Applications of Coding Theory in Computational Complexity
• Automata, Languages and Programming
• Universal service-providers for private information retrieval
• Pseudorandom generators without the XOR lemma

This page was built for publication: On locally decodable codes, self-correctable codes, and \(t\)-private PIR