Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
From MaRDI portal
Publication:5419122
DOI10.1145/1993636.1993705zbMath1288.05153arXiv1009.4375OpenAlexW2145012723MaRDI QIDQ5419122
Zeev Dvir, Boaz Barak, Avi Wigderson, Amir Yehudayoff
Publication date: 5 June 2014
Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.4375
Other designs, configurations (05B30) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Erd?s problems and related topics of discrete geometry (52C10)
Related Items (14)
Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Unnamed Item ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin. ⋮ Unnamed Item ⋮ Sets of unit vectors with small subset sums ⋮ Sylvester-Gallai for arrangements of subspaces ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ On Sums of Locally Testable Affine Invariant Properties ⋮ Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ An ensemble of high rank matrices arising from tournaments ⋮ SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY ⋮ IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM
This page was built for publication: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
