1 Search Results for "Shkredov, Ilya"


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

Authors: Alex Samorodnitsky, Ilya Shkredov, and Sergey Yekhanin

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
A square matrix V is called rigid if every matrix V' 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 paper we propose such a candidate property that has the potential of establishing rigidity of combinatorial design matrices over the field F_2. Stated informally, we conjecture that under a suitable embedding of F_2^n into R^n, vectors arising from a low dimensional F_2-linear space 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.

Cite as

Alex Samorodnitsky, Ilya Shkredov, and Sergey Yekhanin. Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 347-364, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{samorodnitsky_et_al:LIPIcs.CCC.2015.347,
  author =	{Samorodnitsky, Alex and Shkredov, Ilya and Yekhanin, Sergey},
  title =	{{Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{347--364},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.347},
  URN =		{urn:nbn:de:0030-drops-50703},
  doi =		{10.4230/LIPIcs.CCC.2015.347},
  annote =	{Keywords: Matrix rigidity, linear codes, Kolmogorov width}
}
  • Refine by Author
  • 1 Samorodnitsky, Alex
  • 1 Shkredov, Ilya
  • 1 Yekhanin, Sergey

  • Refine by Classification

  • Refine by Keyword
  • 1 Kolmogorov width
  • 1 Matrix rigidity
  • 1 linear codes

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail