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

DOI10.1145/2077336.2077338zbMath1322.94110MaRDI QIDQ2947559

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

lower bounds; locally decodable codes

Mathematics Subject Classification ID

94B60: Other types of codes

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68P05: Data structures

94B35: Decoding