Some structural properties of low-rank matrices related to computational complexity
From MaRDI portal
Publication:1978702
DOI10.1016/S0304-3975(99)00185-1zbMATH Open0938.68059MaRDI QIDQ1978702FDOQ1978702
Giovanni Resta, Pavel Pudlák, Bruno Codenotti
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Concerning nonnegative matrices and doubly stochastic matrices
- Combinatorial matrix theory
- Intersection Theorems for Systems of Sets
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- A note on matrix rigidity
- Top-down lower bounds for depth-three circuits
- The rank and size of graphs
- Boolean Circuits, Tensor Ranks, and Communication Complexity
- Explicit Ramsey graphs and orthonormal labelings
- On finite set-systems whose every intersection is a kernel of a star
- On rank vs. communication complexity
- Large sets of nearly orthogonal vectors
- Matrix Factorization over $GF(2)$ and Trace-Orthogonal Bases of $GF(2^n )$
Cited In (22)
- On Some Open Questions for Ramsey and Folkman Numbers
- Lovász, Vectors, Graphs and Codes
- Constructive lower bounds for off-diagonal Ramsey numbers
- Perturbed Identity Matrices Have High Rank: Proof and Applications
- Fractional \(L\)-intersecting families
- On covering graphs by complete bipartite subgraphs
- Sets of unit vectors with small subset sums
- Hasse diagrams with large chromatic number
- Matrix rank and communication complexity
- Rigidity of a simple extended lower triangular matrix
- On the correlation measures of subsets
- Some constructive bounds on Ramsey numbers
- A polynomial-time algorithm for computing low CP-rank decompositions
- On a theorem of Razborov
- A small step forwards on the Erdős-Sós problem concerning the Ramsey numbers \(R(3, k)\)
- On almost-equidistant sets. II
- Title not available (Why is that?)
- On graphs and algebraic graphs that do not contain cycles of length 4
- Matrix rigidity
- Orthonormal representations of \(H\)-free graphs
- Some recent results on Ramsey-type numbers
- Small Sample Spaces Cannot Fool Low Degree Polynomials
This page was built for publication: Some structural properties of low-rank matrices related to computational complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978702)
