Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length

DOI10.1145/2077336.2077338MaRDI QIDQ2947559zbMATH OpenOpenAlexFDO

Authors Anna Gál, Andrew R. Mills

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2011/3053/

zbMATH Keywords

locally decodable codeslower bounds

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35) Other types of codes (94B60)

Recommendations

• Three query locally decodable codes with higher correctness require exponential length
• 3-query locally decodable codes of subexponential length
• 3-query locally decodable codes of subexponential length
• Towards 3-query locally decodable codes of subexponential length
• Query-efficient locally decodable codes of subexponential 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
• Local correctability of expander codes

Cited in

(12)

• Smooth and strong PCPs
• A quadratic lower bound for three-query linear locally decodable codes over any field
• Three query locally decodable codes with higher correctness require exponential length
• Corruption and Recovery-Efficient Locally Decodable Codes
• Towards 3-query locally decodable codes of subexponential length
• A quadratic lower bound for three-query linear locally decodable codes over any field
• Superquadratic lower bound for 3-query locally correctable codes over the reals
• 3-query locally decodable codes of subexponential length
• 3-query locally decodable codes of subexponential length
• Breaking the quadratic barrier for 3-LCC's over the reals
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Lower bounds for adaptive locally decodable codes

This page was built for publication: Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length

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