Tight lower bounds for linear 2-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
From MaRDI portal
(Redirected from Publication:519967)
Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
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
- scientific article; zbMATH DE number 953255 (Why is no real title available?)
- A Mathematical Theory of Communication
- A new proof of Szemerédi's theorem for arithmetic progressions of length four
- A statistical theorem of set addition
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Locally Decodable Codes
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Lower bounds for linear locally decodable codes and private information retrieval
- On a question of Erdős and Moser
- 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
- Perturbed Identity Matrices Have High Rank: Proof and Applications
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
Cited in
(10)- Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
- Lower bounds for 2-query LCCs over large alphabet
- A generalized sylvester-gallai type theorem for quadratic polynomials
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Sylvester-Gallai type theorems for approximate collinearity
- Breaking the quadratic barrier for 3-LCC's over the reals
- Superquadratic lower bound for 3-query locally correctable codes over the reals
- Lower bounds for constant query affine-invariant LCCs and LTCs
- A finitary structure theorem for vertex-transitive graphs of polynomial growth
- A generalized Sylvester–Gallai-type theorem for quadratic polynomials
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)
