3-query locally decodable codes of subexponential length

DOI10.1145/1536414.1536422zbMath1304.94124OpenAlexW2102801247MaRDI QIDQ5172696

Klim Efremenko

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536422

zbMATH Keywords

locally decodable codesprivate information retrieval schemesPIR schemes

Mathematics Subject Classification ID

Cryptography (94A60) Other types of codes (94B60) Information storage and retrieval of data (68P20) Decoding (94B35)

Related Items (34)

Convex Bodies Associated to Tensor Norms ⋮ A general theory of tensor products of convex sets in Euclidean spaces ⋮ Tweakable block ciphers secure beyond the birthday bound in the ideal cipher model ⋮ A quadratic lower bound for three-query linear locally decodable codes over any field ⋮ CNF-FSS and Its Applications ⋮ Constructing Ramsey graphs from Boolean function representations ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Query-efficient locally decodable codes of subexponential length ⋮ A novel elementary construction of matching vectors ⋮ Communication-efficient distributed oblivious transfer ⋮ Homomorphic secret sharing for low degree polynomials ⋮ On matrix rigidity and locally self-correctable codes ⋮ Foundations of Homomorphic Secret Sharing ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Locally Decodable Codes: A Brief Survey ⋮ Learning Read-Constant Polynomials of Constant Degree Modulo Composites ⋮ On the geometry of projective tensor products ⋮ Learning read-constant polynomials of constant degree modulo composites ⋮ Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Locally Decodable Codes ⋮ Multi-value private information retrieval with colluding databases via trace functions ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ Public Key Locally Decodable Codes with Short Keys ⋮ Short Locally Testable Codes and Proofs ⋮ Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Breaking the Circuit Size Barrier for Secure Computation Under DDH ⋮ Outlaw distributions and locally decodable codes ⋮ High-rate codes with sublinear-time decoding ⋮ A combination of testability and decodability by tensor products ⋮ Local correctability of expander codes

This page was built for publication: 3-query locally decodable codes of subexponential length