Towards 3-query locally decodable codes of subexponential length

DOI10.1145/1326554.1326555zbMATH Open1311.94125OpenAlexW1998698985MaRDI QIDQ3546358FDOQ3546358

Authors: Sergey Yekhanin 

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

Recommendations

• 3-query locally decodable codes of subexponential length
• 3-query locally decodable codes of subexponential length
• Query-efficient locally decodable codes of subexponential length
• Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
• Three query locally decodable codes with higher correctness require exponential length
• A quadratic lower bound for three-query linear locally decodable codes over any field
• A quadratic lower bound for three-query linear locally decodable codes over any field
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Superquadratic lower bound for 3-query locally correctable codes over the reals

Mathematics Subject Classification ID

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

Cited In (48)

• 3-query locally decodable codes of subexponential length
• Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
• Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes
• Constructing Ramsey graphs from Boolean function representations
• On the optimal communication complexity of error-correcting multi-server PIR
• 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
• Multiple correlation sequences not approximable by nilsequences
• Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers
• High-entropy dual functions over finite fields and locally decodable codes
• Private Locally Decodable Codes
• 3-query locally decodable codes of subexponential length
• A quadratic lower bound for three-query linear locally decodable codes over any field
• Near-optimal private information retrieval with preprocessing
• Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
• On the power of relaxed local decoding algorithms
• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
• Towards breaking the exponential barrier for general secret sharing
• A combination of testability and decodability by tensor products
• A novel elementary construction of matching vectors
• Erasures versus errors in local decoding and property testing
• Relaxed locally correctable codes
• High-rate codes with sublinear-time decoding
• Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
• Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Three query locally decodable codes with higher correctness require exponential length
• On matrix rigidity and locally self-correctable codes
• \textsf{TreePIR}: sublinear-time and polylog-bandwidth private information retrieval from DDH
• Relaxed locally correctable codes
• Corruption and Recovery-Efficient Locally Decodable Codes
• Local correctability of expander codes
• Locally decodable codes: a brief survey
• Matching vector codes
• Single-server private information retrieval with sublinear amortized time
• On the inner product predicate and a generalization of matching vector families
• Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
• Private information retrieval with sublinear online time
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Query-efficient locally decodable codes of subexponential length
• From irreducible representations to locally decodable codes
• Private information retrieval with result verification for more servers
• Robust characterizations of \(k\)-wise independence over product spaces and related testing results
• On locally decodable codes, self-correctable codes, and \(t\)-private PIR
• On locally decodable codes in resource bounded channels
• Locally Decodable Codes
• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546358)