Complexity Lower Bounds using Linear Algebra

DOI10.1561/0400000011zbMath1176.68084OpenAlexW2137442467MaRDI QIDQ3397730

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)

Related Items (28)

Complexity of linear circuits and geometry ⋮ Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ Matrix and tensor rigidity and \(L_p\)-approximation ⋮ Approximate Degree in Classical and Quantum Computing ⋮ The landscape of communication complexity classes ⋮ Matrix rigidity of random Toeplitz matrices ⋮ Fourier and Circulant Matrices are Not Rigid ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ A linear algebraic view of partition regular matrices ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ A new lower bound for the positive semidefinite minimum rank of a graph ⋮ Kolmogorov width and approximate rank ⋮ Arithmetic circuits, structured matrices and (not so) deep learning ⋮ Linear algebraic methods in communication complexity ⋮ On rigid matrices and \(U\)-polynomials ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ On a theorem of Razborov ⋮ On matrix rigidity and locally self-correctable codes ⋮ Parameterized low-rank binary matrix approximation ⋮ Using elimination theory to construct rigid matrices ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Matrix Rigidity from the Viewpoint of Parameterized Complexity ⋮ Lower bounds for matrix factorization ⋮ Fourier and circulant matrices are not rigid ⋮ Lower bounds for matrix factorization ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM

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