Towards 3-query locally decodable codes of subexponential length
From MaRDI portal
Publication:3546358
DOI10.1145/1326554.1326555zbMath1311.94125MaRDI 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
Unnamed Item, High-entropy dual functions over finite fields and locally decodable codes, On the Power of Relaxed Local Decoding Algorithms, Multiple correlation sequences not approximable by nilsequences, Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs, Relaxed Locally Correctable Codes, Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs, A combination of testability and decodability by tensor products, High-rate codes with sublinear-time decoding, Unnamed Item, Locally Decodable Codes, 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, 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, Constructing Ramsey graphs from Boolean function representations, A novel elementary construction of matching vectors, On matrix rigidity and locally self-correctable codes, Towards breaking the exponential barrier for general secret sharing, Query-efficient locally decodable codes of subexponential length, Private information retrieval with sublinear online time, Single-server private information retrieval with sublinear amortized time, Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification, Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes, A general private information retrieval scheme for MDS coded databases with colluding servers, Local correctability of expander codes, A quadratic lower bound for three-query linear locally decodable codes over any field, Robust characterizations of k -wise independence over product spaces and related testing results, Locally Decodable Codes: A Brief Survey, Limits on the Rate of Locally Testable Affine-Invariant Codes
