Improved rank bounds for design matrices and a new proof of Kelly's theorem
From MaRDI portal
Publication:2879417
Abstract: We study the rank of complex sparse matrices in which the supports of different columns have small intersections. The rank of these matrices, called design matrices, was the focus of a recent work by Barak et. al. (BDWY11) in which they were used to answer questions regarding point configurations. In this work we derive near-optimal rank bounds for these matrices and use them to obtain asymptotically tight bounds in many of the geometric applications. As a consequence of our improved analysis, we also obtain a new, linear algebraic, proof of Kelly's theorem, which is the complex analog of the Sylvester-Gallai theorem.
Recommendations
- Rank bounds for design matrices with block entries and geometric applications
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
- Fractional Sylvester–Gallai theorems
- On a conjecture of Kelly on (1, 3)-representation of Sylvester-Gallai designs
- Sylvester-Gallai for arrangements of subspaces
Cites work
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 3241005 (Why is no real title available?)
- scientific article; zbMATH DE number 3040001 (Why is no real title available?)
- A Generalization of a Theorem of Sylvester on the Lines Determined by a Finite Point Set.
- A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- A linear lower bound on the unbounded error probabilistic communication complexity.
- A resolution of the Sylvester-Gallai problem of J.-P. Serre
- A survey of Sylvester's problem and its generalizations
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Complexity Lower Bounds using Linear Algebra
- From sylvester-gallai configurations to rank bounds
- Incidence theorems and their applications
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- On Double Diagonal and Cross Latin Squares
- On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR
- On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its applications to error correcting codes
- Perturbed Identity Matrices Have High Rank: Proof and Applications
- Polarities, quasi-symmetric designs, and Hamada's conjecture
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
- Scalings of matrices which have prespecified row sums and column sums via optimization
- Sylvester-Gallai theorems for complex numbers and quaternions
- The minimum rank of symmetric matrices described by a graph: a survey
- Tight Lower Bounds for 2-query LCCs over Finite Fields
Cited in
(15)- Sylvester-Gallai type theorems for approximate collinearity
- Lower bounds for 2-query LCCs over large alphabet
- On a conjecture of Kelly on (1, 3)-representation of Sylvester-Gallai designs
- On the p-rank of the design matrix of a difference set
- Rank bounds for design matrices with block entries and geometric applications
- Sylvester-Gallai for arrangements of subspaces
- Sylvester-Gallai for arrangements of subspaces
- A quantitative variant of the multi-colored Motzkin-Rabin theorem
- A generalized Sylvester–Gallai-type theorem for quadratic polynomials
- A generalized sylvester-gallai type theorem for quadratic polynomials
- A Sylvester-Gallai-type theorem for complex-representable matroids
- On the number of ordinary lines determined by sets in complex space
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
- Equiangular lines and spherical codes in Euclidean space
- Arithmetic circuits: a chasm at depth 3
This page was built for publication: Improved rank bounds for design matrices and a new proof of Kelly's theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2879417)
