Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes

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

zbMATH Keywords

matrix rigiditymatrix scalingSylvester Gallai

Mathematics Subject Classification ID

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