Some structural properties of low-rank matrices related to computational complexity

DOI10.1016/S0304-3975(99)00185-1zbMath0938.68059MaRDI QIDQ1978702

Pavel Pudlák, Giovanni Resta, Bruno Codenotti

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Ramsey numbermatrix rigiditycycles in graphslow-rank matriceslinear circuits

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (20)

On graphs and algebraic graphs that do not contain cycles of length 4 ⋮ A small step forwards on the Erdős-Sós problem concerning the Ramsey numbers \(R(3, k)\) ⋮ Some recent results on Ramsey-type numbers ⋮ On almost-equidistant sets. II ⋮ On the correlation measures of subsets ⋮ Unnamed Item ⋮ Orthonormal representations of \(H\)-free graphs ⋮ On a theorem of Razborov ⋮ Small Sample Spaces Cannot Fool Low Degree Polynomials ⋮ Matrix rigidity ⋮ Lovász, Vectors, Graphs and Codes ⋮ Perturbed Identity Matrices Have High Rank: Proof and Applications ⋮ Rigidity of a simple extended lower triangular matrix ⋮ Fractional \(L\)-intersecting families ⋮ Constructive lower bounds for off-diagonal Ramsey numbers ⋮ Some constructive bounds on Ramsey numbers ⋮ Sets of unit vectors with small subset sums ⋮ On covering graphs by complete bipartite subgraphs ⋮ On Some Open Questions for Ramsey and Folkman Numbers ⋮ Hasse diagrams with large chromatic number

Cites Work

• A note on matrix rigidity
• On finite set-systems whose every intersection is a kernel of a star
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Large sets of nearly orthogonal vectors
• Explicit Ramsey graphs and orthonormal labelings
• Top-down lower bounds for depth-three circuits
• On rank vs. communication complexity
• Concerning nonnegative matrices and doubly stochastic matrices
• Intersection Theorems for Systems of Sets
• Matrix Factorization over $GF(2)$ and Trace-Orthogonal Bases of $GF(2^n )$
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• The rank and size of graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some structural properties of low-rank matrices related to computational complexity