RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Mat. Zametki, 1998, Volume 63, Issue 4, Pages 535–540 (Mi mz1314)  

This article is cited in 24 scientific papers (total in 24 papers)

Improved lower bounds on the rigidity of Hadamard matrices

B. S. Kashin, A. A. Razborov

Steklov Mathematical Institute, Russian Academy of Sciences

Abstract: We write$f=\Omega(g)$ if $f(x)\ge cg(x)$ with some positive constant $c$ for all $x$ from the domain of functions $f$ and $g$. We show that at least $\Omega(n^2/r)$ entries must be changed in an arbitrary (generalized) Hadamard matrix in order to reduce its rank below $r$. This improves the previously known bound $\Omega(n^2/r^2)$. If we additionally know that the changes are bounded above in absolute value by some number $\theta\ge n/r$, then the number of these entries is bounded below by $\Omega(n^3/(r\theta^2))$, which improves upon the previously known bound $\Omega(n^2/\theta^2)$.

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

Full text: PDF file (205 kB)
References: PDF file   HTML file

English version:
Mathematical Notes, 1998, 63:4, 471–475

Bibliographic databases:

UDC: 519.142+517.984.4
Received: 01.12.1997

Citation: B. S. Kashin, A. A. Razborov, “Improved lower bounds on the rigidity of Hadamard matrices”, Mat. Zametki, 63:4 (1998), 535–540; Math. Notes, 63:4 (1998), 471–475

Citation in format AMSBIB
\Bibitem{KasRaz98}
\by B.~S.~Kashin, A.~A.~Razborov
\paper Improved lower bounds on the rigidity of Hadamard matrices
\jour Mat. Zametki
\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}


Linking options:
  • http://mi.mathnet.ru/eng/mz1314
  • https://doi.org/10.4213/mzm1314
  • http://mi.mathnet.ru/eng/mz/v63/i4/p535

    SHARE: 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

    This publication is cited in the following articles:
    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  mathscinet  zmath  isi  scopus
    24. Grochow J.A., “New Applications of the Polynomial Method: the Cap Set Conjecture and Beyond”, Bull. Amer. Math. Soc., 56:1 (2019), 29–64  crossref  mathscinet  zmath  isi  scopus
  • Математические заметки Mathematical Notes
    Number of views:
    This page:840
    Full text:176
    References:64
    First page:3

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020