A remark on matrix rigidity
From MaRDI portal
Publication:293150
DOI10.1016/S0020-0190(97)00190-7zbMath1337.15004OpenAlexW2064269488MaRDI QIDQ293150
Mohammad Amin Shokrollahi, Daniel A. Spielman, Volker 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
Combinatorics in computer science (68R05) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Vector spaces, linear dependence, rank, lineability (15A03)
Related Items (23)
Complexity of linear circuits and geometry ⋮ Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ Matrix rigidity of random Toeplitz matrices ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ Possible numbers of ones in 0–1 matrices with a given rank ⋮ On rigid matrices and \(U\)-polynomials ⋮ More on average case vs approximation complexity ⋮ On a theorem of Razborov ⋮ Min-rank conjecture for log-depth circuits ⋮ Using elimination theory to construct rigid matrices ⋮ Matrix rigidity ⋮ Matrix Rigidity from the Viewpoint of Parameterized Complexity ⋮ Learning Complexity vs Communication Complexity ⋮ Complexity measures of sign matrices ⋮ Rigidity of a simple extended lower triangular matrix ⋮ Rigid matrices from rectangular PCPs ⋮ Lower bounds for matrix factorization ⋮ Fourier and circulant matrices are not rigid ⋮ On the rigidity of Vandermonde matrices ⋮ Lower bounds for matrix factorization ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
Cites Work
This page was built for publication: A remark on matrix rigidity
