A note on matrix rigidity
From MaRDI portal
Publication:684412
DOI10.1007/BF01303207zbMath0848.15005MaRDI QIDQ684412
Publication date: 15 September 1993
Published in: Combinatorica (Search for Journal in Brave)
11T71: Algebraic coding theory; cryptography (number-theoretic aspects)
15B33: Matrices over special rings (quaternions, finite fields, etc.)
15A03: Vector spaces, linear dependence, rank, lineability
Related Items
Matrix Rigidity from the Viewpoint of Parameterized Complexity, A remark on matrix rigidity, Complexity of linear circuits and geometry, Kolmogorov width of discrete linear spaces: an approach to matrix rigidity, More on average case vs approximation complexity, On a theorem of Razborov, Using elimination theory to construct rigid matrices, Min-rank conjecture for log-depth circuits, On approximation by \(^{\oplus}\)-OBDDs, On rigid matrices and \(U\)-polynomials, Rigidity of a simple extended lower triangular matrix, Entropy of operators or why matrix multiplication is hard for depth-two circuits, Improved lower bounds on the rigidity of Hadamard matrices, The computational complexity of some problems of linear algebra, Lower bounds for polynomial evaluation and interpolation problems, On the rigidity of Vandermonde matrices, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, Matrix rigidity, Some structural properties of low-rank matrices related to computational complexity
Cites Work