Tight lower bounds for linear 2-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
From MaRDI portal
Publication:519967
DOI10.1007/S00493-015-3024-ZzbMATH Open1374.94885OpenAlexW2282998501MaRDI QIDQ519967FDOQ519967
Authors: 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
Recommendations
- Lower bounds for 2-query LCCs over large alphabet
- Lower bounds for constant query affine-invariant LCCs and LTCs
- Lower bounds for constant query affine-invariant LCCs and LTCs
- An upper bound for the complexity of linearized coverings in a finite field
- Lower bounds on the linear complexity of the discrete logarithm in finite fields
- Lower bounds for approximate LDCs
- An improvement of bilinear complexity bounds in some finite fields.
- STACS 2005
- A Lower Bound on the Complexity of Polynomial Multiplication over Finite Fields
- On linear complexity of binary lattices. II
Cites Work
- A Mathematical Theory of Communication
- A new proof of Szemerédi's theorem for arithmetic progressions of length four
- On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
- Perturbed Identity Matrices Have High Rank: Proof and Applications
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Title not available (Why is that?)
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- On a question of Erdős and Moser
- A statistical theorem of set addition
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
- Locally Decodable Codes
- On locally decodable codes, self-correctable codes, and \(t\)-private PIR
- Lower bounds for linear locally decodable codes and private information retrieval
Cited In (10)
- Sylvester-Gallai type theorems for approximate collinearity
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Superquadratic lower bound for 3-query locally correctable codes over the reals
- Lower bounds for 2-query LCCs over large alphabet
- Breaking the quadratic barrier for 3-LCC's over the reals
- Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
- A generalized Sylvester–Gallai-type theorem for quadratic polynomials
- A generalized sylvester-gallai type theorem for quadratic polynomials
- Lower bounds for constant query affine-invariant LCCs and LTCs
- A finitary structure theorem for vertex-transitive graphs of polynomial growth
This page was built for publication: Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q519967)
