Some structural properties of low-rank matrices related to computational complexity
From MaRDI portal
Publication:1978702
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)
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
