Abstract
The rigidity of a matrix A with respect to the rank bound r is the minimum number of entries of A that must be changed to reduce the rank of A to or below r. It is a major unsolved problem (Valiant, 1977) to construct “explicit” families of n × n matrices of rigidity n 1 + δ for r=εn, where ε and δ are positive constants. In fact, no superlinear lower bounds are known for explicit families of matrices for rank bound r=Ω(n).
In this paper we give the first optimal, Ω(n 2), lower bound on the rigidity of two “somewhat explicit” families of matrices with respect to the rank bound r=cn, where c is an absolute positive constant. The entries of these matrix families are (i) square roots of n 2 distinct primes and (ii) primitive roots of unity of prime orders for the first n 2 primes. Our proofs use an algebraic dimension concept introduced by Shoup and Smolensky (1997) and a generalization of that concept.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Babai, L., Frankl, P.: Linear Algebra Methods in Combinatorics. Prelim. version 2. Dept. Computer Science. University of Chicago, Chicago (1992)
Baur, W.: Simplified Lower Bounds for Polynomials with Algebraic Coefficients. Journal of Complexity 13, 38–41 (1997)
Besicovitch, A.S.: On the linear independence of fractional powers of integers. J. London Math. Soc. 15, 3–6 (1940)
Bürgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften, vol. 315. Springer, Heidelberg (1997)
Cheraghchi, M.: On Matrix Rigidity and the Complexity of Linear Forms. Electronic Colloquium on Computational Complexity (ECCC) Report CCC TR05-070 (July 2005), Available at http://eccc.uni-trier.de/eccc-reports/2005/TR05-070/index.html
Codenotti, B.: Matrix rigidity. Linear Algebra and its Applications 304(1-3), 181–192 (2000)
Cai, J., Bach, E.: On testing for zero polynomials by a set of points with bounded precision. Theor. Comput. Sci. 296(1), 15–25 (2003)
Chen, Z., Kao, M.: Reducing randomness via Irrational Numbers. In: Proc. 29th Symp. Theory of Computing (STOC), pp. 200–209 (1997)
de Wolf, R.: Lower Bounds on Matrix Rigidity via a Quantum Argument. arXiv.org e-Print quant-ph/0505188, Avaialble at http://arxiv.org/PScache/quant-ph/pdf/0505/0505188.pdf
Friedman, J.: A note on Matrix Rigidity. Combinatorica 13(2), 235–239 (1993)
von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (1999)
Kashin, B., Razborov, A.A.: Improved Lower Bounds on the Rigidity of Hadamard Matrices (Russian). Matematicheskie Zametki 63(4), 535–540 (1998), English translation is available at http://genesis.mi.ras.ru/~razborov/hadamard.ps
Lang, S.: Algebra, 3rd edn. Addison-Wesley Publishing Company, Reading (1993)
Lickteig, T.: Ein elementarer Beweis fr eine geometrische Gradschranke fr die Zahl der Operationen bei der Berechnung von Polynomen. In: Diplomarbeit, Univ. Konstanz (1980)
Lokam, S.V.: On the Rigidity of Vandermonde Matrices. Theoretical Computer Science 237(1-2), 477–483 (2000)
Lewin, D., Vadhan, S.: Checking Polynomial Identities over any Field: Towards a Derandomization? In: Proc. 30th Symp. Theory of Computing (STOC), pp. 438–447 (1998)
Pudlák, P., Rödl, V.: Some Combinatorial-Algebraic Problems from Complexity Theory. Discrete Mathematics 136, 253–279 (1994)
Shoup, V., Smolensky, R.: Lower Bounds for Polynomial Evaluation and Interpolation. Computational Complexity 6(4), 301–311 (1997)
Shokrollahi, M.A., Spielman, D.A., Stemann, V.: A Remark on Matrix Rigidity. Information Processing Letters 64(6), 283–285 (1997)
Valiant, L.G.: Graph-Theoretic Arguments in Low-level Complexity. In: Proc. 6th Math. Foundations of Comp. Sci. Lecture notes in Computer Science, vol. 53, pp. 162–176. Springer, Heidelberg (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lokam, S.V. (2006). Quadratic Lower Bounds on Matrix Rigidity. In: Cai, JY., Cooper, S.B., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2006. Lecture Notes in Computer Science, vol 3959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11750321_28
Download citation
DOI: https://doi.org/10.1007/11750321_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34021-8
Online ISBN: 978-3-540-34022-5
eBook Packages: Computer ScienceComputer Science (R0)