Superquadratic lower bound for 3-query locally correctable codes over the reals

DOI10.4086/TOC.2017.V013A011zbMATH Open1375.94176OpenAlexW2786800728MaRDI QIDQ4591373FDOQ4591373

Authors: Zeev Dvir, A. Wigderson, Shubhangi Saraf 

Publication date: 14 November 2017

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2017.v013a011

Recommendations

• Breaking the quadratic barrier for 3-LCC's over the reals
• 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
• Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
• Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length

zbMATH Keywords

combinatoricsdiscrete geometrylower boundscoding theory

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Bounds on codes (94B65)

Cited In (9)

• The Paulsen problem made simple
• On the power of relaxed local decoding algorithms
• Breaking the quadratic barrier for 3-LCC's over the reals
• The Paulsen problem made simple
• Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
• Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
• Towards 3-query locally decodable codes of subexponential length
• A strongly polynomial algorithm for approximate Forster transforms and its application to halfspace learning
• A Quiver Invariant Theoretic Approach to Radial Isotropy and the Paulsen Problem for Matrix Frames

This page was built for publication: Superquadratic lower bound for 3-query locally correctable codes over the reals

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