Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
type: Item
instance of: scholarly article
title: Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
zbMATH Open document ID: 1006.68051
author: Satyanarayana V. Lokam
published in: Journal of Computer and System Sciences
publication date: 2002-07-04T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1763392
zbMATH Keywords: rigidity of a matrix
zbMATH Keywords: communication complexity
MaRDI profile type: Publication
full work available at URL: jcss.2001.1786
OpenAlex ID: W1996146326
cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: Q4331740
cites work: Arithmetization: A new method in structural complexity theory
cites work: Q4190138
cites work: On lower bounds for read-\(k\)-times branching programs
cites work: A note on matrix rigidity
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: Q5185900
cites work: Relations between communication complexity classes
cites work: The variation of the spectrum of a normal matrix
cites work: Improved lower bounds on the rigidity of Hadamard matrices
cites work: Algebraic methods for interactive proof systems
cites work: Q4231904
cites work: On the rigidity of Vandermonde matrices
cites work: Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
cites work: Q4234123
cites work: Communication in bounded depth circuits
cites work: Some combinatorial-algebraic problems from complexity theory
cites work: Boolean Circuits, Tensor Ranks, and Communication Complexity
cites work: Probabilistic communication complexity
cites work: Q3990226
cites work: IP = SPACE
cites work: IP = PSPACE
cites work: Lower bounds for polynomial evaluation and interpolation problems
cites work: A remark on matrix rigidity
cites work: Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Q4164821
DOI: 10.1006/JCSS.2001.1786
Recommended article: Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
Recommended article: On the Complexity of Matrix Rank and Rigidity
Recommended article: On the complexity of matrix rank and rigidity
Recommended article: Matrix Rigidity from the Viewpoint of Parameterized Complexity
Recommended article: Q3721690
Recommended article: Efficient Calculation of Bounds on Spectra of Hessian Matrices
Recommended article: Communication lower bounds and optimal algorithms for numerical linear algebra
Recommended article: Strict spectral approximation of a matrix and some related problems
Recommended article: The matrix ridge approximation: algorithms and applications
description: scientific article; zbMATH DE number 1763392