A note on matrix rigidity
From MaRDI portal
Publication:684412
DOI10.1007/BF01303207zbMath0848.15005OpenAlexW2008671178MaRDI QIDQ684412
Publication date: 15 September 1993
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01303207
Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Vector spaces, linear dependence, rank, lineability (15A03)
Related Items (28)
A remark on matrix rigidity ⋮ Complexity of linear circuits and geometry ⋮ Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ On approximation by \(^{\oplus}\)-OBDDs ⋮ Matrix rigidity of random Toeplitz matrices ⋮ Fourier and Circulant Matrices are Not Rigid ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ Lower bounds for polynomial evaluation and interpolation problems ⋮ 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 ⋮ Some structural properties of low-rank matrices related to computational complexity ⋮ Matrix Rigidity from the Viewpoint of Parameterized Complexity ⋮ Rigidity of a simple extended lower triangular matrix ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ The computational complexity of some problems of linear algebra ⋮ Lower bounds for matrix factorization ⋮ Fourier and circulant matrices are not rigid ⋮ On the rigidity of Vandermonde matrices ⋮ Improved lower bounds on the rigidity of Hadamard matrices ⋮ Lower bounds for matrix factorization ⋮ The computational complexity of some problems of linear algebra ⋮ 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 note on matrix rigidity
