Complexity Lower Bounds using Linear Algebra

DOI10.1561/0400000011MaRDI QIDQ3397730zbMATH OpenOpenAlexFDO

Authors Satyanarayana V. Lokam

Publication date 25 September 2009

Published in Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1561/0400000011

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Linear algebraic methods in communication complexity
• Algebraic techniques in communication complexity
• scientific article; zbMATH DE number 139642
• Some combinatorial-algebraic problems from complexity theory
• Applications of matrix methods to the theory of lower bounds in computational complexity

Cited in

(44)

• Algebraic techniques in communication complexity
• Linear complexity algorithm for semiseparable matrices
• The landscape of communication complexity classes
• Matrix rigidity of random Toeplitz matrices
• A new lower bound for the positive semidefinite minimum rank of a graph
• Lower bounds for matrix factorization
• Matrix and tensor rigidity and L_p-approximation
• Parameterized low-rank binary matrix approximation
• Kolmogorov width and approximate rank
• Improved rank bounds for design matrices and a new proof of Kelly's theorem
• Randomized communication complexity for linear algebra problems over finite fields
• Complexity of linear circuits and geometry
• Kolmogorov width of discrete linear spaces: an approach to matrix rigidity
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Linear FPT reductions and computational lower bounds
• Linear algebraic methods in communication complexity
• On a theorem of Razborov
• Interval Linear Algebra and Computational Complexity
• New applications of the polynomial method: the cap set conjecture and beyond
• Sign rank versus Vapnik-Chervonenkis dimension
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Using elimination theory to construct rigid matrices
• Approximate Degree in Classical and Quantum Computing
• Fourier and circulant matrices are not rigid
• Lower bounds for matrix factorization
• On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
• Fourier and circulant matrices are not rigid
• Efficient Construction of Rigid Matrices Using an NP Oracle
• A linear algebraic view of partition regular matrices
• Arithmetic circuits, structured matrices and (not so) deep learning
• On matrix rigidity and locally self-correctable codes
• Rigid matrices from rectangular PCPs
• Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity
• Determinants vs. algebraic branching programs
• Widths and rigidity
• Determinants vs. algebraic branching programs
• Efficient construction of rigid matrices using an NP oracle
• Bounded simultaneous messages
• Widths and rigidity of unconditional sets and random vectors
• Lower bounds for planar arithmetic circuits
• A polynomial degree bound on equations for non-rigid matrices and small linear circuits
• Circuit depth reductions
• Kronecker products, low-depth circuits, and matrix rigidity
• On rigid matrices and \(U\)-polynomials

This page was built for publication: Complexity Lower Bounds using Linear Algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3397730)