IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM

DOI10.1017/fms.2014.2zbMath1317.52020arXiv1211.0330OpenAlexW2132463883MaRDI QIDQ2879417

Avi Wigderson, Zeev Dvir, Shubhangi Saraf

Publication date: 1 September 2014

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.0330

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) Theory of computing (68Q99)

Related Items

On a conjecture of Kelly on (1, 3)-representation of Sylvester-Gallai designs ⋮ A generalized Sylvester–Gallai-type theorem for quadratic polynomials ⋮ On the number of ordinary lines determined by sets in complex space ⋮ Equiangular lines and spherical codes in Euclidean space ⋮ Unnamed Item ⋮ Sylvester-Gallai type theorems for quadratic polynomials ⋮ Rank bounds for design matrices with block entries and geometric applications ⋮ Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling ⋮ A quantitative variant of the multi-colored Motzkin-Rabin theorem ⋮ Sylvester-Gallai for arrangements of subspaces ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials ⋮ SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its applications to error correcting codes
• The minimum rank of symmetric matrices described by a graph: a survey
• Polarities, quasi-symmetric designs, and Hamada's conjecture
• A resolution of the Sylvester-Gallai problem of J.-P. Serre
• Scalings of matrices which have prespecified row sums and column sums via optimization
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Sylvester-Gallai theorems for complex numbers and quaternions
• A survey of Sylvester's problem and its generalizations
• Incidence Theorems and Their Applications
• Complexity Lower Bounds using Linear Algebra
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR
• On Double Diagonal and Cross Latin Squares
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• From sylvester-gallai configurations to rank bounds
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Tight Lower Bounds for 2-query LCCs over Finite Fields
• A Generalization of a Theorem of Sylvester on the Lines Determined by a Finite Point Set.
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents