RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. заметки:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Матем. заметки, 1998, том 63, выпуск 4, страницы 535–540 (Mi mz1314)  

Эта публикация цитируется в 23 научных статьях (всего в 23 статьях)

Новые нижние оценки устойчивости матриц Адамара

Б. С. Кашин, А. А. Разборов

Математический институт им. В. А. Стеклова РАН

Аннотация: Пусть соотношение $f=\Omega(g)$ означает, что $f(x)\ge cg(x)$ для некоторой положительной постоянной $c$ и для всех $x$ из области определения функций $f$ и $g$. Показано, что в произвольной (обобщенной) матрице Адамара необходимо изменить по крайней мере $\Omega(n^2/r)$ элементов, для того чтобы ранг полученной матрицы не превосходил $r$. Это улучшает ранее известную оценку $\Omega(n^2/r^2)$. Если дополнительно потребовать, чтобы измененные элементы были ограничены сверху по модулю некоторой величиной $\theta\ge n/r$, то справедлива другая оценка $\Omega(n^3/(r\theta^2))$, усиливающая предыдущую $\Omega(n^2/\theta^2)$.
Библиография: 20 названий.

DOI: https://doi.org/10.4213/mzm1314

Полный текст: PDF файл (205 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Mathematical Notes, 1998, 63:4, 471–475

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.142+517.984.4
Поступило: 01.12.1997

Образец цитирования: Б. С. Кашин, А. А. Разборов, “Новые нижние оценки устойчивости матриц Адамара”, Матем. заметки, 63:4 (1998), 535–540; Math. Notes, 63:4 (1998), 471–475

Цитирование в формате AMSBIB
\RBibitem{KasRaz98}
\by Б.~С.~Кашин, А.~А.~Разборов
\paper Новые нижние оценки устойчивости матриц Адамара
\jour Матем. заметки
\yr 1998
\vol 63
\issue 4
\pages 535--540
\mathnet{http://mi.mathnet.ru/mz1314}
\crossref{https://doi.org/10.4213/mzm1314}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1680943}
\zmath{https://zbmath.org/?q=an:0917.15013}
\transl
\jour Math. Notes
\yr 1998
\vol 63
\issue 4
\pages 471--475
\crossref{https://doi.org/10.1007/BF02311250}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000075783100029}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mz1314
  • https://doi.org/10.4213/mzm1314
  • http://mi.mathnet.ru/rus/mz/v63/i4/p535

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Pudlák P., “A note on the use of determinant for proving lower bounds on the size of linear circuits”, Inform. Process. Lett., 74:5-6 (2000), 197–201  crossref  mathscinet  zmath  isi
    2. Lokam S.V., “On the rigidity of Vandermonde matrices”, Theoret. Comput. Sci., 237:1-2 (2000), 477–483  crossref  mathscinet  zmath  isi  scopus  scopus
    3. Forster J., Simon H.U., “On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes uniform distribution”, Algorithmic learning theory, Lecture Notes in Comput. Sci., 2533, Springer, Berlin, 2002, 128–138  crossref  mathscinet  zmath  isi
    4. Alekhnovich M., “More on Average Case Vs Approximation Complexity”, 44th Annual IEEE Symposium on Foundations of Computer Science, Proceedings, Annual IEEE Symposium on Foundations of Computer Science, ed. Titsworth F., IEEE Computer Soc, 2003, 298–307  crossref  isi  scopus  scopus
    5. Forster J, Simon H.U., “On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes”, Theoret. Comput. Sci., 350:1 (2006), 40–48  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    6. de Wolf R., “Lower bounds on matrix rigidity via a quantum argument”, Automata, languages and programming, Part I, Lecture Notes in Comput. Sci., 4051, Springer, Berlin, 2006, 62–71  crossref  mathscinet  zmath  isi
    7. Lokam S.V., “Quadratic lower bounds on matrix rigidity”, Theory and applications of models of computation, Lecture Notes in Comput. Sci., 3959, Springer, Berlin, 2006, 295–307  crossref  mathscinet  zmath  isi  scopus  scopus
    8. Linial N., Mendelson Sh., Schechtman G., Shraibman A., “Complexity measures of sign matrices”, Combinatorica, 27:4 (2007), 439–463  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    9. Klivans A.R., Sherstov A.A., “A Lower Bound for Agnostically Learning Disjunctions”, Learning Theory, Proceedings, Lecture Notes in Computer Science, 4539, eds. Bshouty N., Gentile C., Springer-Verlag Berlin, 2007, 409–423  crossref  mathscinet  zmath  isi
    10. Keevash P., “Shadows and intersections: stability and new proofs”, Adv. Math., 218:5 (2008), 1685–1703  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    11. Linial N., Shraibman A., “Learning Complexity Vs. Communication Complexity”, Twenty-Third Annual IEEE Conference on Computational Complexity, Proceedings, Annual IEEE Conference on Computational Complexity, IEEE Computer Soc, 2008, 53–63  crossref  mathscinet  isi  scopus  scopus
    12. Linial N., Shraibman A., “Learning complexity vs. communication complexity”, Combin. Probab. Comput., 18:1-2 (2009), 227–245  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    13. Alon N., Panigrahy R., Yakhanin S., “Deterministic Approximation Algorithms for the Nearest Codeword Problem”, Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Computer Science, 5687, eds. Dinur I., Jansen K., Naor J., Rolim J., Springer-Verlag Berlin, 2009, 339–351  crossref  mathscinet  zmath  isi  scopus  scopus
    14. Klivans A.R., Sherstov A.A., “Lower Bounds for Agnostic Learning via Approximate Rank”, Comput. Complex., 19:4 (2010), 581–604  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    15. Alekhnovich M., “More on Average Case Vs Approximation Complexity”, Comput. Complex., 20:4, SI (2011), 755–786  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    16. Sherstov A.A., “The Unbounded-Error Communication Complexity of Symmetric Functions”, Combinatorica, 31:5 (2011), 583–614  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    17. Jukna S., Schnitger G., “Min-Rank Conjecture for Log-Depth Circuits”, J. Comput. Syst. Sci., 77:6, SI (2011), 1023–1038  crossref  mathscinet  zmath  isi  scopus  scopus
    18. Saraf Sh., Yekhanin S., “Noisy Interpolation of Sparse Polynomials, and Applications”, 2011 IEEE 26th Annual Conference on Computational Complexity (Ccc), Annual IEEE Conference on Computational Complexity, IEEE Computer Soc, 2011, 86–92  crossref  mathscinet  isi  scopus  scopus
    19. Alon N., Cohen G., “on Rigid Matrices and U-Polynomials”, 2013 IEEE Conference on Computational Complexity (Ccc), IEEE Conference on Computational Complexity, IEEE, 2013, 197–206  crossref  mathscinet  isi  scopus
    20. Alon N., Cohen G., “on Rigid Matrices and U-Polynomials”, Comput. Complex., 24:4 (2015), 851–879  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    21. Samorodnitsky A., Shkredov I., Yekhanin S., “Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity”, Comput. Complex., 25:2, SI (2016), 309–348  crossref  mathscinet  zmath  isi  elib  scopus
    22. Gesmundo F., Hauenstein J.D., Ikenmeyer Ch., Landsberg J.M., “Complexity of Linear Circuits and Geometry”, Found. Comput. Math., 16:3 (2016), 599–635  crossref  mathscinet  zmath  isi  scopus
    23. Alman J., Williams R., “Probabilistic Rank and Matrix Rigidity”, Stoc'17: Proceedings of the 49Th Annual Acm Sigact Symposium on Theory of Computing, Annual Acm Symposium on Theory of Computing, eds. Hatami H., McKenzie P., King V., Assoc Computing Machinery, 2017, 641–652  crossref  isi
  • Математические заметки Mathematical Notes
    Просмотров:
    Эта страница:691
    Полный текст:110
    Литература:55
    Первая стр.:3

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018