Towards 3-query locally decodable codes of subexponential length
From MaRDI portal
Publication:3546358
DOI10.1145/1326554.1326555zbMath1311.94125OpenAlexW1998698985MaRDI QIDQ3546358
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1326554.1326555
Related Items (34)
A quadratic lower bound for three-query linear locally decodable codes over any field ⋮ Towards breaking the exponential barrier for general secret sharing ⋮ Single-server private information retrieval with sublinear amortized time ⋮ Multiple correlation sequences not approximable by nilsequences ⋮ Unnamed Item ⋮ Constructing Ramsey graphs from Boolean function representations ⋮ 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 ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ On the optimal communication complexity of error-correcting multi-server PIR ⋮ \textsf{TreePIR}: sublinear-time and polylog-bandwidth private information retrieval from DDH ⋮ Query-efficient locally decodable codes of subexponential length ⋮ A novel elementary construction of matching vectors ⋮ On matrix rigidity and locally self-correctable codes ⋮ Relaxed Locally Correctable Codes ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Locally Decodable Codes: A Brief Survey ⋮ Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes ⋮ Unnamed Item ⋮ Locally Decodable Codes ⋮ High-entropy dual functions over finite fields and locally decodable codes ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ Private information retrieval with sublinear online time ⋮ Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ High-rate codes with sublinear-time decoding ⋮ A general private information retrieval scheme for MDS coded databases with colluding servers ⋮ A combination of testability and decodability by tensor products ⋮ Robust characterizations of k -wise independence over product spaces and related testing results ⋮ 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 ⋮ Local correctability of expander codes
This page was built for publication: Towards 3-query locally decodable codes of subexponential length
