Improved lower bounds on the rigidity of Hadamard matrices

DOI10.1007/BF02311250zbMath0917.15013OpenAlexW2029734507MaRDI QIDQ1280658

Boris S. Kashin, Alexander A. Razborov

Publication date: 15 March 1999

Published in: Mathematical Notes (Search for Journal in Brave)

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

zbMATH Keywords

Hadamard matrixlower boundsspectral methodsrigidity of matrices

Mathematics Subject Classification ID

Inequalities involving eigenvalues and eigenvectors (15A42)

Related Items (15)

A note on the use of determinant for proving lower bounds on the size of linear circuits ⋮ Complexity of linear circuits and geometry ⋮ Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ On rigid matrices and \(U\)-polynomials ⋮ The unbounded-error communication complexity of symmetric functions ⋮ More on average case vs approximation complexity ⋮ Min-rank conjecture for log-depth circuits ⋮ Matrix rigidity ⋮ Shadows and intersections: Stability and new proofs ⋮ Learning Complexity vs Communication Complexity ⋮ Complexity measures of sign matrices ⋮ On the rigidity of Vandermonde matrices ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity ⋮ On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes

Cites Work

• A note on matrix rigidity
• Operator norms of submatrices
• Communication in bounded depth circuits
• Almost orthogonal submatrices of an orthogonal matrix
• The variation of the spectrum of a normal matrix
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved lower bounds on the rigidity of Hadamard matrices