Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ilya Shkredov:

TR14-172 | 12th December 2014
Alex Samorodnitsky, Ilya Shkredov, Sergey Yekhanin

Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

A square matrix $V$ is called rigid if every matrix $V^\prime$ obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major ... more >>>

ISSN 1433-8092 | Imprint