A remark on matrix rigidity

DOI10.1016/S0020-0190(97)00190-7MaRDI QIDQ293150zbMATH OpenOpenAlexFDO

Authors M. Amin Shokrollahi, Daniel A. Spielman, V. Stemann

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019097001907?np=y

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Combinatorics in computer science (68R05) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Recommendations

• A note on matrix rigidity
• Theory and Applications of Models of Computation
• scientific article; zbMATH DE number 37868
• On the rigidity of Vandermonde matrices
• Matrix rigidity

Cites work

• A note on matrix rigidity
• Communication in bounded depth circuits
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 37868 (Why is no real title available?)
• scientific article; zbMATH DE number 48941 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1261801 (Why is no real title available?)

Cited in

(35)

• On the rigidity of Vandermonde matrices
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Matrix rigidity of random Toeplitz matrices
• Matrix rigidity
• Lower bounds for matrix factorization
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• Using elimination theory to construct rigid matrices
• Complexity of linear circuits and geometry
• Kolmogorov width of discrete linear spaces: an approach to matrix rigidity
• Learning complexity vs communication complexity
• Lower Bounds on Matrix Rigidity Via a Quantum Argument
• scientific article; zbMATH DE number 37868 (Why is no real title available?)
• More on average case vs approximation complexity
• On a theorem of Razborov
• New applications of the polynomial method: the cap set conjecture and beyond
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Using elimination theory to construct rigid matrices
• Fourier and circulant matrices are not rigid
• Lower bounds for matrix factorization
• Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory
• Possible numbers of ones in 0–1 matrices with a given rank
• Matrix rigidity of random toeplitz matrices
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Theory and Applications of Models of Computation
• Matrix rigidity depends on the target field
• Rigid matrices from rectangular PCPs
• Min-rank conjecture for log-depth circuits
• A note on matrix rigidity
• Efficient construction of rigid matrices using an NP oracle
• Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
• Block rigidity: strong multiplayer parallel repetition implies super-linear lower bounds for Turing machines
• On rigid matrices and \(U\)-polynomials
• Complexity measures of sign matrices
• Rigidity of a simple extended lower triangular matrix

This page was built for publication: A remark on matrix rigidity

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