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

DOI10.1145/2077336.2077338zbMath1322.94110OpenAlexW2128636284MaRDI QIDQ2947559

Andrew R. Mills, Anna Gál

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

lower boundslocally decodable codes

Mathematics Subject Classification ID

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

Related Items (2)

A quadratic lower bound for three-query linear locally decodable codes over any field ⋮ Smooth and strong PCPs

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