Outlaw distributions and locally decodable codes

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