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:

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. Pudlá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
2. Lokam S.V., “On the rigidity of Vandermonde matrices”, Theoret. Comput. Sci., 237:1-2 (2000), 477–483
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
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
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
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
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
8. Linial N., Mendelson Sh., Schechtman G., Shraibman A., “Complexity measures of sign matrices”, Combinatorica, 27:4 (2007), 439–463
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
10. Keevash P., “Shadows and intersections: stability and new proofs”, Adv. Math., 218:5 (2008), 1685–1703
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
12. Linial N., Shraibman A., “Learning complexity vs. communication complexity”, Combin. Probab. Comput., 18:1-2 (2009), 227–245
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
14. Klivans A.R., Sherstov A.A., “Lower Bounds for Agnostic Learning via Approximate Rank”, Comput. Complex., 19:4 (2010), 581–604
15. Alekhnovich M., “More on Average Case Vs Approximation Complexity”, Comput. Complex., 20:4, SI (2011), 755–786
16. Sherstov A.A., “The Unbounded-Error Communication Complexity of Symmetric Functions”, Combinatorica, 31:5 (2011), 583–614
17. Jukna S., Schnitger G., “Min-Rank Conjecture for Log-Depth Circuits”, J. Comput. Syst. Sci., 77:6, SI (2011), 1023–1038
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
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
20. Alon N., Cohen G., “on Rigid Matrices and U-Polynomials”, Comput. Complex., 24:4 (2015), 851–879
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
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
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
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
•  Number of views: This page: 874 Full text: 196 References: 66 First page: 3

 Contact us: math-net2020_12 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2020