A note on matrix rigidity

DOI10.1007/BF01303207MaRDI QIDQ684412zbMATH OpenOpenAlexFDO

Authors Joel Friedman

Publication date 15 September 1993

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01303207

zbMATH Keywords

rankfinite fieldtheory of algebraic codes

Mathematics Subject Classification ID

Matrices over special rings (quaternions, finite fields, etc.) (15B33) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Vector spaces, linear dependence, rank, lineability (15A03)

Recommendations

• A remark on matrix rigidity
• Matrix rigidity
• Using elimination theory to construct rigid matrices
• Theory and Applications of Models of Computation
• scientific article; zbMATH DE number 37868

Cited in

(37)

• Fourier and circulant matrices are not rigid
• Lower bounds for matrix factorization
• Lower Bounds on Matrix Rigidity Via a Quantum Argument
• Lower bounds for matrix factorization
• Fourier and circulant matrices are not rigid
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• On approximation by \(^{\oplus}\)-OBDDs
• Kolmogorov width of discrete linear spaces: an approach to matrix rigidity
• Lower bounds for polynomial evaluation and interpolation problems
• A remark on matrix rigidity
• More on average case vs approximation complexity
• The computational complexity of some problems of linear algebra (extended abstract)
• Complexity of linear circuits and geometry
• Kolmogorov width of discrete linear spaces: an approach to matrix rigidity
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Using elimination theory to construct rigid matrices
• On matrix rigidity and locally self-correctable codes
• Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory
• On rigid matrices and \(U\)-polynomials
• Rigidity of a simple extended lower triangular matrix
• Improved lower bounds on the rigidity of Hadamard matrices
• Matrix rigidity depends on the target field
• Using elimination theory to construct rigid matrices
• On the rigidity of Vandermonde matrices
• Matrix rigidity of random toeplitz matrices
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• On a theorem of Razborov
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Rigid matrices from rectangular PCPs
• Matrix rigidity
• Some structural properties of low-rank matrices related to computational complexity
• Min-rank conjecture for log-depth circuits
• The computational complexity of some problems of linear algebra
• Matrix rigidity of random Toeplitz matrices
• Entropy of operators or why matrix multiplication is hard for depth-two circuits
• New applications of the polynomial method: the cap set conjecture and beyond

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

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