3-Query Locally Decodable Codes of Subexponential Length

DOI10.1137/090772721zbMath1311.94124OpenAlexW2027317757MaRDI QIDQ4910581

Klim Efremenko

Publication date: 19 March 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090772721

zbMATH Keywords

locally decodable codesprivate information retrieval

Mathematics Subject Classification ID

Other types of codes (94B60) Decoding (94B35)

Related Items (21)

Towards breaking the exponential barrier for general secret sharing ⋮ Single-server private information retrieval with sublinear amortized time ⋮ Secure computation with preprocessing via function secret sharing ⋮ Unnamed Item ⋮ Erasures versus errors in local decoding and property testing ⋮ Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ On the optimal communication complexity of error-correcting multi-server PIR ⋮ \textsf{TreePIR}: sublinear-time and polylog-bandwidth private information retrieval from DDH ⋮ Relaxed Locally Correctable Codes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the modulo degree complexity of Boolean functions ⋮ High-entropy dual functions over finite fields and locally decodable codes ⋮ Private information retrieval with sublinear online time ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ A general private information retrieval scheme for MDS coded databases with colluding servers ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

This page was built for publication: 3-Query Locally Decodable Codes of Subexponential Length