Outlaw distributions and locally decodable codes
From MaRDI portal
Publication:4638069
DOI10.4230/LIPIcs.ITCS.2017.20zbMath1402.94121arXiv1609.06355OpenAlexW2963507783MaRDI QIDQ4638069
Zeev Dvir, Jop Briët, Sivakanth Gopi
Publication date: 3 May 2018
Full work available at URL: https://arxiv.org/abs/1609.06355
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (2)
On the Power of Relaxed Local Decoding Algorithms ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Mathematical Theory of Communication
- Locally decodable codes and the failure of cotype for projective tensor products
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Lower bounds for linear locally decodable codes and private information retrieval
- Entropy and the combinatorial dimension
- Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory
- A quadratic lower bound for three-query linear locally decodable codes over any field
- Discrepancy and eigenvalues of Cayley graphs
- 2-Server PIR with Sub-Polynomial Communication
- On the Locality of Codeword Symbols
- Proof verification and the hardness of approximation problems
- Private information retrieval
- On the efficiency of local decoding procedures for error-correcting codes
- Explicit Concentrators from Generalized N-Gons
- Expander graphs and their applications
- Probabilistic checking of proofs
- Random Cayley graphs and expanders
- Designing programs that check their work
- Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound
- High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
- Quasirandom Cayley graphs
- 3-query locally decodable codes of subexponential length
- Upper and Lower Bounds for Stochastic Processes
- High-rate codes with sublinear-time decoding
- Locally Decodable Codes
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
This page was built for publication: Outlaw distributions and locally decodable codes