Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity

DOI10.1006/jcss.2001.1786zbMath1006.68051OpenAlexW1996146326MaRDI QIDQ1604200

Satyanarayana V. Lokam

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

zbMATH Keywords

communication complexityrigidity of a matrix

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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