Towards 3-query locally decodable codes of subexponential length
From MaRDI portal
Publication:3546358
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
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)