### DIMACS Theoretical Computer Science Seminar

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

Speaker: **Sergey Yekhanin**, Microsoft

Date: Wednesday, April 1, 2015 9:30am**

**Note special time

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

A square matrix V is called rigid if every matrix 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 implications in computational
complexity theory. One approach to establishing rigidity of a matrix V
is to come up with a property that is satisfied by any collection of
vectors arising from a low-dimensional space, but is not satisfied 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 field. 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).

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S15/