Bulletin of the American Mathematical Society

Author(s): J. M. Landsberg
Journal: Bull. Amer. Math. Soc. 45 (2008), 247-284.
MSC (2000): Primary 68Q17
Posted: January 7, 2008
Retrieve article in: PDF DVI PostScript

Abstract: We survey results in algebraic complexity theory, focusing on matrix multiplication. Our goals are (i) to show how open questions in algebraic complexity theory are naturally posed as questions in geometry and representation theory, (ii) to motivate researchers to work on these questions, and (iii) to point out relations with more general problems in geometry. The key geometric objects for our study are the secant varieties of Segre varieties. We explain how these varieties are also useful for algebraic statistics, the study of phylogenetic invariants, and quantum computing.

1.: H. Abo, G. Ottaviani, and P. Peterson, Induction for secant varieties of Segre varieties, preprint, math.AG/0607191.
2.: A. Alder and V. Strassen, On the algorithmic complexity of associative algebras, Theoret. Comput. Sci. 15 (1981), no. 2, 201-211. MR 623595 (82g:68038)
3.: Valery B. Alekseyev, On the complexity of some algorithms of matrix multiplication, J. Algorithms 6 (1985), no. 1, 71-85. MR 780851 (86g:68070)
4.: J. Alexander and A. Hirschowitz, Polynomial interpolation in several variables, J. Algebraic Geom. 4 (1995), no. 2, 201-222. MR 1311347 (96f:14065)
5.: Elizabeth S. Allman and John A. Rhodes, Phylogenetic ideals and varieties for the general Markov model, Advances in Applied Mathematics (to appear).
6.: -, Phylogenetic invariants for the general Markov model of sequence mutation, Math. Biosci. 186 (2003), no. 2, 113-144. MR 2024609 (2004j:92048)
7.: Wolf Barth, Submanifolds of low codimension in projective space, Proceedings of the International Congress of Mathematicians (Vancouver, B.C., 1974), Vol. 1, Canad. Math. Congress, Montreal, Que., 1975, pp. 409-413. MR 0422294 (54:10285)
8.: Ingemar Bengtsson and Karol Życzkowski, Geometry of quantum states, Cambridge University Press, Cambridge, 2006, An Introduction to Quantum Entanglement. MR 2230995
9.: Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti, $O(n\sp{2.7799})$ complexity for $n\times n$ approximate matrix multiplication, Inform. Process. Lett. 8 (1979), no. 5, 234-235. MR 534068 (80h:68024)
10.: Markus Bläser, A $\frac52 n\sp 2$ -lower bound for the rank of $n\times n$ -matrix multiplication over arbitrary fields, 40th Annual Symposium on Foundations of Computer Science (New York, 1999), IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 45-50. MR 1916183
11.: -, On the complexity of the multiplication of matrices of small formats, J. Complexity 19 (2003), no. 1, 43-60. MR 1951322 (2003k:68040)
12.: M. Brambilla and G. Ottaviani, On the Alexander-Hirschowitz theorem, preprint math.AG/0701409.
13.: Roger W. Brockett and David Dobkin, On the optimal evaluation of a set of bilinear forms, Linear Algebra and Appl. 19 (1978), no. 3, 207-235. MR 0495183 (58:13915)
14.: Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997, with the collaboration of Thomas Lickteig. MR 1440179 (99c:68002)
15.: M. V. Catalisano, A. V. Geramita, and A. Gimigliano, On the rank of tensors, via secant varieties and fat points, Zero-Dimensional Schemes and Applications (Naples, 2000), Queen's Papers in Pure and Appl. Math., vol. 123, Queen's Univ., Kingston, ON, 2002, pp. 133-147. MR 1898833
16.: -, Ranks of tensors, secant varieties of Segre varieties and fat points, Linear Algebra Appl. 355 (2002), 263-285. MR 1930149 (2003g:14070)
17.: -, Higher secant varieties of Segre-Veronese varieties, Projective Varieties with Unexpected Properties, Walter de Gruyter GmbH & Co. KG, Berlin, 2005, pp. 81-107. MR 2202248
18.: -, Secant varieties of Grassmann varieties, Proc. Amer. Math. Soc. 133 (2005), no. 3, 633-642 (electronic). MR 2113908 (2006d:14053)
19.: M.V. Catalisano, A.V. Geramita, and A. Gimigliano, On the ideals of secant varieties to certain rational varieties, preprint math.AG/0609054.
20.: J.A. Cavender and J. Felsenstein, Invariants of phylogenies in a simple case with discrete states, J. Classification 4 (1987), 57-71.
21.: Ciro Ciliberto, Geometric aspects of polynomial interpolation in more variables and of Waring's problem, European Congress of Mathematics, Vol. I (Barcelona, 2000), Progr. Math., vol. 201, Birkhäuser, Basel, 2001, pp. 289-316. MR 1905326 (2003i:14058)
22.: H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans, Group-theoretic algorithms for matrix multiplication, Proceedings of the 46th Annual Symposium on Foundations of Computer Science (2005), 379-388.
23.: H. Cohn and C. Umans, A group theoretic approach to fast matrix multiplication, Proceedings of the 44th Annual Symposium on Foundations of Computer Science (2003), no. 2, 438-449.
24.: Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251-280. MR 1056627 (91i:68058)
25.: J. Eisert and D. Gross, Multi-particle entanglement, Lectures on Quantum Information (D. Bruss and G. Leuchs, eds.), Wiley-VCH, Weinheim, 2006, pp. 237-252.
26.: Jens Eisert and Hans J. Briegel, Schmidt measure as a tool for quantifying multiparticle entanglement, Phys. Rev. A 64 (2001), no. 022306, 1-4.
27.: William Fulton and Joe Harris, Representation theory, A first course, Graduate Texts in Mathematics, vol. 129, Readings in Mathematics, Springer-Verlag, New York, 1991. MR 1153249 (93a:20069)
28.: Luis David Garcia, Michael Stillman, and Bernd Sturmfels, Algebraic geometry of Bayesian networks, J. Symbolic Comput. 39 (2005), no. 3-4, 331-355. MR 2168286 (2006g:68242)
29.: Joe Harris, Algebraic geometry, A first course, Graduate Texts in Mathematics, vol. 133, Springer-Verlag, New York, 1995, corrected reprint of the 1992 original. MR 1182558 (93j:14001)
30.: Robin Hartshorne, Varieties of small codimension in projective space, Bull. Amer. Math. Soc. 80 (1974), 1017-1032. MR 0384816 (52:5688)
31.: J. E. Hopcroft and L. R. Kerr, On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math. 20 (1971), 30-36. MR 0274293 (43:58)
32.: Serkan Hoşten and Suela Ruffa, Introductory notes to algebraic statistics, Rend. Istit. Mat. Univ. Trieste 37 (2005), no. 1-2, 39-70 (2006). MR 2227048
33.: Thomas A. Ivey and J. M. Landsberg, Cartan for beginners: differential geometry via moving frames and exterior differential systems, Graduate Studies in Mathematics, vol. 61, American Mathematical Society, Providence, RI, 2003. MR 2003610 (2004g:53002)
34.: Julian D. Laderman, A noncommutative algorithm for multiplying $3\times 3$ matrices using multiplications, Bull. Amer. Math. Soc. 82 (1976), no. 1, 126-128. MR 0395320 (52:16117)
35.: James A. Lake, A rate-independent technique for analysis of nucleic acid sequences: evolutionary parsimony, Mol. Biol. Evol. 4 (1987), no. 2, 167-191.
36.: J. M. Landsberg, The border rank of the multiplication of $2\times2$ matrices is seven, J. Amer. Math. Soc. 19 (2006), no. 2, 447-459 (electronic). MR 2188132 (2006j:68034)
37.: J. M. Landsberg and L. Manivel, On the ideals of secant varieties of Segre varieties, Found. Comput. Math. 4 (2004), no. 4, 397-422. MR 2097214 (2005m:14101)
38.: J. M. Landsberg and Laurent Manivel, On the projective geometry of rational homogeneous varieties, Comment. Math. Helv. 78 (2003), no. 1, 65-100. MR 1966752 (2004a:14050)
39.: J.M. Landsberg and L. Manivel, Generalizations of Strassen's equations for Secant varieties of Segre varieties, Communications in Algebra 36 (2008), 1-18.
40.: J.M. Landsberg and J. Morton, Computational complexity and geometry, book in preparation.
41.: J.M. Landsberg and J. Weyman, On the ideals and singularities of secant varieties of Segre varieties, preprint, math.AG/0601452, Bull. London Math. Soc. 39 (2007), no. 4, 685-697. MR 2346950
42.: R. Lazarsfeld and A. Van de Ven, Topics in the geometry of projective space, DMV Seminar, vol. 4, Birkhäuser Verlag, Basel, 1984, recent work of F. L. Zak, with an addendum by Zak. MR 808175 (87e:14045)
43.: Thomas Lickteig, A note on border rank, Inform. Process. Lett. 18 (1984), no. 3, 173-178. MR 760371 (86c:68040)
44.: -, Typical tensorial rank, Linear Algebra Appl. 69 (1985), 95-120. MR 798367 (87f:15017)
45.: G. Ottaviani, Symplectic bundles on the plane, secant varieties and Lüroth quartics revisited, preprint, math.AG/0702151.
46.: Giorgio Ottaviani and Elena Rubei, Quivers and the cohomology of homogeneous vector bundles, Duke Math. J. 132 (2006), no. 3, 459-508. MR 2219264
47.: Lior Pachter and Bernd Sturmfels (eds.), Algebraic statistics for computational biology, Cambridge University Press, New York, 2005. MR 2205865 (2006i:92002)
48.: A. Schönhage, Partial and total matrix multiplication, SIAM J. Comput. 10 (1981), no. 3, 434-455. MR 623057 (82h:68070)
49.: Jean-Pierre Serre, Linear representations of finite groups, Springer-Verlag, New York, 1977, translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42. MR 0450380 (56:8675)
50.: F. Severi, Sintorno ai punti doppi impropri di una superficie generale dello spazio a quattro dimensioni, e a suio punti tripli apparenti, Rend. Circ. Mat. Palermo 15 (1901), no. 2, 33-51.
51.: J. Sidman and S. Sullivant, Secant varieties and prolongations, preprint, arXiv:math/0611696.
52.: V. Strassen, Rank and optimal computation of generic tensors, Linear Algebra Appl. 52/53 (1983), 645-685. MR 709378 (85b:15039)
53.: -, Relative bilinear complexity and matrix multiplication, J. Reine Angew. Math. 375/376 (1987), 406-443. MR 882307 (88h:11026)
54.: Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354-356. MR 0248973 (40:2223)
55.: R. C. Vaughan and T. D. Wooley, Waring's problem: a survey, Number Theory for the Millennium, III (Urbana, IL, 2000), A K Peters, Natick, MA, 2002, pp. 301-340. MR 1956283 (2003j:11116)
56.: Abraham Waksman, On Winograd's algorithm for inner products, IEEE Trans. Computers C-19 (1970), no. 4, 360-361. MR 0455534 (56:13772)
57.: Jerzy Weyman, Cohomology of vector bundles and syzygies, Cambridge Tracts in Mathematics, vol. 149, Cambridge University Press, Cambridge, 2003. MR 1988690 (2004d:13020)
58.: S. Winograd, On multiplication of $2\times 2$ matrices, Linear Algebra and Appl. 4 (1971), 381-388. MR 0297115 (45:6173)
59.: F. L. Zak, Projections of algebraic varieties, Mat. Sb. (N.S.) 116(158) (1981), no. 4, 593-602, 608. MR 665860 (84i:14012)
60.: -, Tangents and secants of algebraic varieties, Translations of Mathematical Monographs, vol. 127, American Mathematical Society, Providence, RI, 1993, translated from the Russian manuscript by the author. MR 1234494 (94i:14053)

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 68Q17

J. M. Landsberg
Affiliation: Department of Mathematics, Texas A&M University, College Station, Texas 77843-3368
Email: jml@math.tamu.edu

DOI: 10.1090/S0273-0979-08-01176-2
PII: S 0273-0979(08)01176-2
Keywords: Border rank, complexity of matrix multiplication, secant varieties
Received by editor(s): November 17, 2006,
Received by editor(s) in revised form: March 12, 2007
Posted: January 7, 2008
Copyright of article: Copyright 2008, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS