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

DOI10.4086/TOC.2017.V013A011MaRDI QIDQ4591373zbMATH OpenOpenAlexFDO

Authors Zeev Dvir, A. Wigderson, Shubhangi Saraf

Publication date 14 November 2017

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

combinatoricsdiscrete geometrylower boundscoding theory

Mathematics Subject Classification ID

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

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

Cited in

(9)

• The Paulsen problem made simple
• On the power of relaxed local decoding algorithms
• The Paulsen problem made simple
• Breaking the quadratic barrier for 3-LCC's over the reals
• 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)