zbMATH — the first resource for mathematics

Improved lower bounds on the rigidity of Hadamard matrices. (English. Russian original) Zbl 0917.15013
Math. Notes 63, No. 4, 471-475 (1998); translation from Mat. Zametki 63, No. 4, 535-540 (1998).
It is proved that for any \(n\times n\) generalized Hadamard matrix \(H\) and any \(r\leq n/2\) the inequality \(R_H^c(r)\geq \Omega(n^2/r)\) holds. Moreover, if \(\theta\) is an additional parameter satisfying \(\theta\geq n/r\), then \(R_H^c(r,\theta)\geq \Omega(n^3/r\theta^2)\). Here, \(R_H^c(r)\) and \(R_H^c(r,\theta)\) are the rigidity functions of \(H\) while \(\Omega(g)=f\) in \(f(x)\geq cg(x)\) with some positive constant \(c\) for all \(x\) from the domain of the functions \(f\) and \(g\).

15A42 Inequalities involving eigenvalues and eigenvectors
Full Text: DOI
[1] L. G. Valiant,Some Conjectures Relating to Superlinear Complexity Bounds, Tech. Report No. 85, Univ. of Leeds (1976).
[2] L. G. Valiant,Graph-Theoretic Arguments in Low-Level Complexity, Tech. Report No. 13-77, Univ. of Edinburgh, Dep. of Comp. Sci. (1977).
[3] D. Yu. Grigor’ev, ”An application of separability and independence notions for obtaining lower bounds of circuit complexity,”Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (POMI),60, 38–48 (1976). · Zbl 0341.94020
[4] D. Yu. Grigor’ev, ”Lower bounds in the algebraic computational complexity,”Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (POMI),118, 25–82 (1982). · Zbl 0504.68024
[5] A. A. Razborov,On Rigid Matrices [in Russian], Manuscript (1989).
[6] S. V. Lokam, ”Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity,” in:Proc. of the 36th IEEE Symposium on Foundations of Computer Science, Los Alamitos (CA), 6–15 (1995). · Zbl 0937.68515
[7] J. Friedman, ”A note on matrix rigidity,”Combinatorica,13, No. 2, 235–239 (1993). · Zbl 0848.15005 · doi:10.1007/BF01303207
[8] P. Pudlák and Z. Vavřín, ”Computation of rigidity of ordern 2 /r for one simple matrix,”Comment. Math. Univ. Carolin.,32, No. 2, 213–218 (1991).
[9] P. Kimmel and A. Settle,Reducing the Rank of Lower Triangular All-Ones Matrix, Tech. Report CS 92-21, Univ. of Chicago (1992).
[10] P. Pudlák, ”Large communication in constant depth circuits,”Combinatorica,14, No. 2, 203–216 (1994). · Zbl 0819.68090 · doi:10.1007/BF01215351
[11] M. Krause and S. Waack, ”Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in,” in:Proc. of the 32nd IEEE Symposium on Foundations of Computer Science, Los Alamitos (CA), 777–782 (1991).
[12] N. Nisan and A. Wigderson, ”On the complexity of bilinear forms,” in:Proc. of the 27th ACM Symposium on the Theory of Computing, New York, 723–732 (1995). · Zbl 1059.68577
[13] P. Pudlák, A. Razborov, and P. Savický,Observations on Rigidity of Hadamard Matrices [in Russian], Manuscript (1988).
[14] N. Alon,On the Rigidity of Hadamard Matrices, Manuscript (1990).
[15] A. J. Hoffman and H. W. Wielandt, ”The variation of the spectrum of a normal matrix,”Duke Math. J.,20, 37–39 (1953). · Zbl 0051.00903 · doi:10.1215/S0012-7094-53-02004-3
[16] G. H. Golub and C. F. van Loan,Matrix Computations, John Hopkins Univ. Press (1983). · Zbl 0559.65011
[17] B. S. Kashin, ”On some properties of matrices of bounded operators from the space 2 n into 2 n , ”Izv. Akad. Nauk Arm. SSR Mat.,15, No. 5, 379–394 (1980). · Zbl 0452.15023
[18] A. A. Lunin, ”Operator norms of submatrices,”Mat. Zametki [Math. Notes]45, No. 3, 248–252 (1989). · Zbl 0687.15021
[19] B. Kashin and L. Tzaffiri,Some Remarks on the Restriction of Operators to Coordinate Subspaces, Tech. Report No. 12, The Edmund Landau Center for Research in Math. Anal., Hebrew Univ., Jerusalem (1993/94).
[20] M. Rudelson, ”Almost orthogonal submatrices of an orthogonal matrix,”Israel J. Math (to appear). · Zbl 0958.15019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.