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

Matematicheskie Zametki

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Forthcoming papers
	Archive
	Impact factor
	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

Matematicheskie Zametki, 1998, Volume 63, Issue 4, Pages 535–540
DOI: https://doi.org/10.4213/mzm1314 (Mi mzm1314)

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

Improved lower bounds on the rigidity of Hadamard matrices

B. S. Kashin, A. A. Razborov

Steklov Mathematical Institute, Russian Academy of Sciences

Full-text PDF (205 kB) Citations (29)

References:

PDF

HTML

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

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)$ .

Received: 01.12.1997

English version:
Mathematical Notes, 1998, Volume 63, Issue 4, Pages 471–475
DOI: https://doi.org/10.1007/BF02311250

Bibliographic databases:

Document Type: Article

UDC: 519.142+517.984.4

Language: Russian

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/mzm1314}

\crossref{https://doi.org/10.4213/mzm1314}

\mathscinet{http://mathscinet.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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000075783100029}

Linking options:

https://www.mathnet.ru/eng/mzm1314

https://doi.org/10.4213/mzm1314

https://www.mathnet.ru/eng/mzm/v63/i4/p535

This publication is cited in the following 29 articles:

M. Rosicka, S. Szarek, A. Rutkowski, P. Gnaciński, M. Horodecki, “Constructive nonlocal games with very small classical values”, Phys. Rev. A, 110:5 (2024)
B. V. Konoplev, “Ob obraschenii funktsii Valianta rangovoi ustoichivosti matritsy”, Materialy 20 Mezhdunarodnoi Saratovskoi zimnei shkoly «Sovremennye problemy teorii funktsii i ikh prilozheniya», Saratov, 28 yanvarya — 1 fevralya 2020 g. Chast 1, Itogi nauki i tekhn. Sovrem. mat. i ee pril. Temat. obz., 199, VINITI RAN, M., 2021, 60–65
Grochow J.A., “New Applications of the Polynomial Method: the Cap Set Conjecture and Beyond”, Bull. Amer. Math. Soc., 56:1 (2019), 29–64
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
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
Gesmundo F., Hauenstein J.D., Ikenmeyer Ch., Landsberg J.M., “Complexity of Linear Circuits and Geometry”, Found. Comput. Math., 16:3 (2016), 599–635
Alon N., Cohen G., “on Rigid Matrices and U-Polynomials”, Comput. Complex., 24:4 (2015), 851–879
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
Alekhnovich M., “More on Average Case Vs Approximation Complexity”, Comput. Complex., 20:4, SI (2011), 755–786
Sherstov A.A., “The Unbounded-Error Communication Complexity of Symmetric Functions”, Combinatorica, 31:5 (2011), 583–614
Jukna S., Schnitger G., “Min-Rank Conjecture for Log-Depth Circuits”, J. Comput. Syst. Sci., 77:6, SI (2011), 1023–1038
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
Klivans A.R., Sherstov A.A., “Lower Bounds for Agnostic Learning via Approximate Rank”, Comput. Complex., 19:4 (2010), 581–604
Linial N., Shraibman A., “Learning complexity vs. communication complexity”, Combin. Probab. Comput., 18:1-2 (2009), 227–245
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
Keevash P., “Shadows and intersections: stability and new proofs”, Adv. Math., 218:5 (2008), 1685–1703
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
Linial N., Mendelson Sh., Schechtman G., Shraibman A., “Complexity measures of sign matrices”, Combinatorica, 27:4 (2007), 439–463
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
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

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

Statistics & downloads:
Abstract page:	1142
Full-text PDF :	316
References:	109
First page:	3

Registration to the website

Logotypes