Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.

DOI10.1007/s00493-015-3024-zzbMath1374.94885OpenAlexW2282998501MaRDI QIDQ519967

Amir Shpilka, Zeev Dvir, Arnab Bhattacharyya, Shubhangi Saraf

Publication date: 31 March 2017

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-015-3024-z

zbMATH Keywords

locally correctable codelocally decodable code

Mathematics Subject Classification ID

Bounds on codes (94B65) Combinatorial aspects of finite geometries (05B25)

Related Items (5)

A generalized Sylvester–Gallai-type theorem for quadratic polynomials ⋮ Unnamed Item ⋮ Zero-free regions of partition functions with applications to algorithms and graph limits ⋮ A finitary structure theorem for vertex-transitive graphs of polynomial growth ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials

Cites Work

• Unnamed Item
• A Mathematical Theory of Communication
• On locally decodable codes, self-correctable codes, and \(t\)-private PIR
• On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
• Lower bounds for linear locally decodable codes and private information retrieval
• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• A statistical theorem of set addition
• On a question of Erdős and Moser
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Locally Decodable Codes
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

This page was built for publication: Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.