Theory of Computing Seminar

Friday May 15, 2015 12:00 PM

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

Speaker: Sergey Yekhanin, Microsoft Research
Location: Annenberg 213


A square matrix V (over any field) is called rigid if every matrix obtained by altering a small number of entries of V has suf∩¼üciently 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 implications in computational complexity theory. One approach to establishing rigidity of a matrix V is to come up with a property that is satis∩¼üed by any collection of vectors arising from a low-dimensional space, but is not satis∩¼üed by the rows of V even after alterations. In this work we propose such a candidate property that has the potential of establishing rigidity of combinatorial design matrices over the binary ∩¼üeld. Stated informally, we conjecture that under a suitable embedding of the Boolean cube into the Euclidian space, vectors arising from a low dimensional linear space modulo two always have somewhat small Kolmogorov width, i.e., admit a non-trivial simultaneous approximation by a low dimensional Euclidean space. This implies rigidity of combinatorial designs, as their rows do not admit such an approximation even after alterations. Our main technical contribution is a collection of results establishing weaker forms and special cases of the conjecture above. 
(Joint work with Alex Samorodnitsky and Ilya Shkredov).
Series Theory of Computing Seminar Series

Contact: Thomas Vidick