Kolmogorov width of discrete linear spaces: an approach to matrix rigidity
From MaRDI portal
Publication:301519
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/
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)
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
