nach oben

Foundations of Computational Mathematics

Erschienen in:

01.06.2016

Complexity of Linear Circuits and Geometry

verfasst von: Fulvio Gesmundo, Jonathan D. Hauenstein, Christian Ikenmeyer, J. M. Landsberg

Erschienen in: Foundations of Computational Mathematics | Ausgabe 3/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We use algebraic geometry to study matrix rigidity and, more generally, the complexity of computing a matrix–vector product, continuing a study initiated in Kumar et al. (2009), Landsberg et al. (preprint). In particular, we (1) exhibit many non-obvious equations testing for (border) rigidity, (2) compute degrees of varieties associated with rigidity, (3) describe algebraic varieties associated with families of matrices that are expected to have super-linear rigidity, and (4) prove results about the ideals and degrees of cones that are of interest in their own right.

Vorheriger Artikel Every Matrix is a Product of Toeplitz Matrices

Nächster Artikel Plane Wave Discontinuous Galerkin Methods: Exponential Convergence of the -Version

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Paolo Aluffi, Degrees of projections of rank loci, preprint arXiv:1408.1702.

E. Arbarello, M. Cornalba, P. A. Griffiths, and J. Harris, Geometry of algebraic curves. Vol. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 267, Springer-Verlag, New York, 1985.

Bruno Codenotti, Matrix rigidity, Linear Algebra Appl. 304 (2000), no. 1–3, 181–192.MathSciNetCrossRefMATH

Ronald de Wolf, Lower bounds on matrix rigidity via a quantum argument, Automata, languages and programming. Part I, Lecture Notes in Comput. Sci., vol. 4051, Springer, Berlin, 2006, pp. 62–71.

Zeev Dvir, On matrix rigidity and locally self-correctable codes, Comput. Complexity 20 (2011), no. 2, 367–388.MathSciNetCrossRefMATH

Joel Friedman, A note on matrix rigidity, Combinatorica 13 (1993), no. 2, 235–239.MathSciNetCrossRefMATH

William Fulton, Intersection theory, second ed., Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 2, Springer-Verlag, Berlin, 1998.

William Fulton and Joe Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991, A first course, Readings in Mathematics.

Joe Harris, Algebraic geometry, Graduate Texts in Mathematics, vol. 133, Springer-Verlag, New York, 1995, A first course, Corrected reprint of the 1992 original.

10.

B. S. Kashin and A. A. Razborov, New lower bounds for the stability of Hadamard matrices, Mat. Zametki 63 (1998), no. 4, 535–540.MathSciNetCrossRefMATH

11.

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, and Jayalal Sarma M. N., Using elimination theory to construct rigid matrices, Foundations of software technology and theoretical computer science—FSTTCS 2009, LIPIcs. Leibniz Int. Proc. Inform., vol. 4, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2009, pp. 299–310.

12.

J. M. Landsberg, Tensors: geometry and applications, Graduate Studies in Mathematics, vol. 128, American Mathematical Society, Providence, RI, 2012.

13.

J. M. Landsberg, J. Taylor, and N. K. Vishnoi, The geometry of matrix rigidity (preprint). https://smartech.gatech.edu/handle/1853/6514.

14.

F. Thomson Leighton, Introduction to parallel algorithms and architectures, Morgan Kaufmann, San Mateo, CA, 1992, Arrays, trees, hypercubes.

15.

Satyanarayana V. Lokam, On the rigidity of Vandermonde matrices, Theoret. Comput. Sci. 237 (2000), no. 1-2, 477–483.MathSciNetCrossRefMATH

16.

Satyanarayana V. Lokam, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, J. Comput. System Sci. 63 (2001), no. 3, 449–473.MathSciNetCrossRefMATH

17.

Satyanarayana V. Lokam, Quadratic lower bounds on matrix rigidity, Theory and applications of models of computation, Lecture Notes in Comput. Sci., vol. 3959, Springer, Berlin, 2006, pp. 295–307.

18.

Satyanarayana V. Lokam, Complexity lower bounds using linear algebra, Found. Trends Theor. Comput. Sci. 4 (2008), no. 1-2, front matter, 1–155 (2009).

19.

Meena Mahajan and Jayalal Sarma M. N., Rigidity of a simple extended lower triangular matrix, Inform. Process. Lett. 107 (2008), no. 5, 149–153.MathSciNetCrossRefMATH

20.

David Mumford, Algebraic geometry. I, Classics in Mathematics, Springer-Verlag, Berlin, 1995, Complex projective varieties, Reprint of the 1976 edition.

21.

David Mumford, The red book of varieties and schemes, expanded ed., Lecture Notes in Mathematics, vol. 1358, Springer-Verlag, Berlin, 1999, Includes the Michigan lectures (1974) on curves and their Jacobians, With contributions by Enrico Arbarello.

22.

Nicholas Pippenger, Superconcentrators, SIAM J. Comput. 6 (1977), no. 2, 298–304.MathSciNetCrossRefMATH

23.

Pavel Pudlák and Zdeněk Vavřín, Computation of rigidity of order \(n^2/r\) for one simple matrix, Comment. Math. Univ. Carolin. 32 (1991), no. 2, 213–218.MathSciNetMATH

24.

M. A. Shokrollahi, D. A. Spielman, and V. Stemann, A remark on matrix rigidity, Inform. Process. Lett. 64 (1997), no. 6, 283–285.MathSciNetCrossRef

25.

Richard P. Stanley, Enumerative combinatorics. Volume 1, second ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012.

26.

Harry Tamvakis, The connection between representation theory and Schubert calculus, Enseign. Math 50 (2004), no. 3-4, 267–286.MathSciNetMATH

27.

Leslie G. Valiant, Graph-theoretic arguments in low-level complexity, Mathematical foundations of computer science (Proc. Sixth Sympos., Tatranská Lomnica, 1977), Springer, Berlin, 1977, pp. 162–176. Lecture Notes in Comput. Sci., Vol. 53.

Titel: Complexity of Linear Circuits and Geometry
verfasst von: Fulvio Gesmundo
Jonathan D. Hauenstein
Christian Ikenmeyer
J. M. Landsberg
Publikationsdatum: 01.06.2016
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 3/2016
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-015-9258-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2016

Reconstruction of Signals from Magnitudes of Redundant Representations: The Complex Case

Approximating Gradients with Continuous Piecewise Polynomial Functions

Plane Wave Discontinuous Galerkin Methods: Exponential Convergence of the -Version

On the Nuclear Norm and the Singular Value Decomposition of Tensors

Numerical Stability in the Presence of Variable Coefficients

Every Matrix is a Product of Toeplitz Matrices

Premium Partner