The Complexity of Local List Decoding

DOI10.1007/978-3-540-85363-3_36zbMath1159.94393OpenAlexW1598233781MaRDI QIDQ3541812

Guy N. Rothblum, Dan Gutfreund

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_36

zbMATH Keywords

constant-depth circuitslist-decodable codeslocally-decodable codes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decoding (94B35)

Related Items

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Erasures versus errors in local decoding and property testing ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Advice Lower Bounds for the Dense Model Theorem