Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
From MaRDI portal
Publication:1604200
DOI10.1006/jcss.2001.1786zbMath1006.68051OpenAlexW1996146326MaRDI QIDQ1604200
Publication date: 4 July 2002
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.2001.1786
Related Items (17)
Complexity of linear circuits and geometry ⋮ Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ The landscape of communication complexity classes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ A variational approach of the rank function ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Expander graphs and their applications ⋮ More on average case vs approximation complexity ⋮ On the Power of Statistical Zero Knowledge ⋮ On a theorem of Razborov ⋮ Min-rank conjecture for log-depth circuits ⋮ Using elimination theory to construct rigid matrices ⋮ Shadows and intersections: Stability and new proofs ⋮ Rigidity of a simple extended lower triangular matrix ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ Verifiable Stream Computation and Arthur--Merlin Communication ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A remark on matrix rigidity
- Probabilistic communication complexity
- A note on matrix rigidity
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Arithmetization: A new method in structural complexity theory
- Relations between communication complexity classes
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Improved lower bounds on the rigidity of Hadamard matrices
- Communication in bounded depth circuits
- Some combinatorial-algebraic problems from complexity theory
- Lower bounds for polynomial evaluation and interpolation problems
- On the rigidity of Vandermonde matrices
- On lower bounds for read-\(k\)-times branching programs
- The variation of the spectrum of a normal matrix
- PP is as Hard as the Polynomial-Time Hierarchy
- The Knowledge Complexity of Interactive Proof Systems
- Algebraic methods for interactive proof systems
- IP = PSPACE
- IP = SPACE
- Boolean Circuits, Tensor Ranks, and Communication Complexity
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
This page was built for publication: Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
