Kolmogorov width of discrete linear spaces: an approach to matrix rigidity

DOI10.1007/s00037-016-0129-8zbMath1344.68100OpenAlexW2338282553MaRDI QIDQ301519

Alex Samorodnitsky, Ilya D. Shkredov, Sergey Yekhanin

Publication date: 30 June 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5070/

zbMATH Keywords

linear codesKolmogorov widthmatrix rigidity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Linear codes (general theory) (94B05) Combinatorial aspects of packing and covering (05B40)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• On matrix rigidity and locally self-correctable codes
• A note on matrix rigidity
• On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its applications to error correcting codes
• On rigid matrices and \(U\)-polynomials
• Polarities, quasi-symmetric designs, and Hamada's conjecture
• Spectral analysis of large dimensional random matrices
• Nonlinear Kolmogorov widths
• Improved lower bounds on the rigidity of Hadamard matrices
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• On \(n\)-dimensional diameters of compacts in a Hilbert space
• On Multiplicative $\lambda$-Approximations and Some Geometric Applications
• Complexity Lower Bounds using Linear Algebra
• Deterministic Approximation Algorithms for the Nearest Codeword Problem
• On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry
• Natural proofs

This page was built for publication: Kolmogorov width of discrete linear spaces: an approach to matrix rigidity