Some structural properties of low-rank matrices related to computational complexity
type: Item
instance of: scholarly article
title: Some structural properties of low-rank matrices related to computational complexity
zbMATH Open document ID: 0938.68059
DOI: 10.1016/S0304-3975(99)00185-1
author: Pavel Pudlák
author: Bruno Codenotti
author: Giovanni Resta
published in: Theoretical Computer Science
publication date: 2000-06-04T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1454436
zbMATH Keywords: matrix rigidity
zbMATH Keywords: low-rank matrices
zbMATH Keywords: cycles in graphs
zbMATH Keywords: Ramsey number
zbMATH Keywords: linear circuits
MaRDI profile type: Publication
cites work: Explicit Ramsey graphs and orthonormal labelings
cites work: Large sets of nearly orthogonal vectors
cites work: Q5737099
cites work: Combinatorial matrix theory
cites work: Intersection Theorems for Systems of Sets
cites work: A note on matrix rigidity
cites work: On finite set-systems whose every intersection is a kernel of a star
cites work: Top-down lower bounds for depth-three circuits
cites work: The rank and size of graphs
cites work: Matrix Factorization over $GF(2)$ and Trace-Orthogonal Bases of $GF(2^n )$
cites work: On rank vs. communication complexity
cites work: Boolean Circuits, Tensor Ranks, and Communication Complexity
cites work: Q3758729
cites work: Q3974988
cites work: Concerning nonnegative matrices and doubly stochastic matrices
cites work: Q4164821
cites work: Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
description: scientific article; zbMATH DE number 1454436