Book Reviews
Book reviews do not contain an abstract.
You may download the entire review from the links below.
- MathSciNet review: 4076536
- Full text review in PDF
- This review is available free of charge
- Geometry and complexity theory by J. M. Landsberg
- Bull. Amer. Math. Soc. 57 (2020), 317-324
- Additional book information: Cambridge Studies in Advanced Mathematics, Vol. 169, Cambridge University Press, Cambridge, 2017, xi+339 pp., ISBN 978-1-107-19923-1, US$64.99
Reviewer information
- Reviewer: Mateusz Michałek
- Affiliation: Max Planck Institute for Mathematics in the Sciences, Institute of Mathematics of the Polish Academy of Sciences, Warsaw, Poland; and, Department of Mathematics and Systems Analysis, Aalto University, Helsinki, Finland
- Email: michalek@mis.mpg.de
References
- Noga Alon, Amir Shpilka, and Christopher Umans, On sunflowers and matrix multiplication, 2012 IEEE 27th Conference on Computational Complexity—CCC 2012, IEEE Computer Soc., Los Alamitos, CA, 2012, pp. 214–223. MR 3026329, DOI 10.1109/CCC.2012.26
- Andris Ambainis, Yuval Filmus, and François Le Gall, Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract), STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 585–593. MR 3388238
- K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
- K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491–567. MR 543793
- Sanjeev Arora and Boaz Barak, Computational complexity, Cambridge University Press, Cambridge, 2009. A modern approach. MR 2500087, DOI 10.1017/CBO9780511804090
- D. Bini, Relations between exact and approximate bilinear algorithms. Applications, Calcolo 17 (1980), no. 1, 87–97. MR 605920, DOI 10.1007/BF02575865
- Markus Bläser, On the complexity of the multiplication of matrices of small formats, J. Complexity 19 (2003), no. 1, 43–60. MR 1951322, DOI 10.1016/S0885-064X(02)00007-9
- Weronika Buczyńska and Jarosław Buczyński, Secant varieties to high degree Veronese reembeddings, catalecticant matrices and smoothable Gorenstein schemes, J. Algebraic Geom. 23 (2014), no. 1, 63–90. MR 3121848, DOI 10.1090/S1056-3911-2013-00595-0
- 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, DOI 10.1007/978-3-662-03338-8
- Luca Chiantini, Jonathan D. Hauenstein, Christian Ikenmeyer, Joseph M. Landsberg, and Giorgio Ottaviani, Polynomials and the exponent of matrix multiplication, Bull. Lond. Math. Soc. 50 (2018), no. 3, 369–389. MR 3829726, DOI 10.1112/blms.12147
- H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans, Group-theoretic algorithms for matrix multiplication, 2005 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 379–388, IEEE, Piscataway, NJ, 2005.
- H. Cohn and C. Umans. A group-theoretic approach to fast matrix multiplication, Proceedings of 2003 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 438–449. IEEE, Piscataway, NJ, 2003.
- Henry Cohn and Christopher Umans, Fast matrix multiplication using coherent configurations, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2012, pp. 1074–1087. MR 3202968
- Pierre Comon, Gene Golub, Lek-Heng Lim, and Bernard Mourrain, Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl. 30 (2008), no. 3, 1254–1279. MR 2447451, DOI 10.1137/060661569
- Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 1–6. ACM, New York, 1987.
- Jan Draisma and Jochen Kuttler, Bounded-rank tensors are defined in bounded degree, Duke Math. J. 163 (2014), no. 1, 35–63. MR 3161311, DOI 10.1215/00127094-2405170
- B. Grenet, An upper bound for the permanent versus determinant problem, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.717.4014 (2011).
- Jonathan D. Hauenstein, Christian Ikenmeyer, and J. M. Landsberg, Equations for lower bounds on border rank, Exp. Math. 22 (2013), no. 4, 372–383. MR 3171099, DOI 10.1080/10586458.2013.825892
- Christopher J. Hillar and Lek-Heng Lim, Most tensor problems are NP-hard, J. ACM 60 (2013), no. 6, Art. 45, 39. MR 3144915, DOI 10.1145/2512329
- 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 274293, DOI 10.1137/0120004
- Julian D. Laderman, A noncommutative algorithm for multiplying $3\times 3$ matrices using $23$ multiplications, Bull. Amer. Math. Soc. 82 (1976), no. 1, 126–128. MR 395320, DOI 10.1090/S0002-9904-1976-13988-2
- J. M. Landsberg, The border rank of the multiplication of $2\times 2$ matrices is seven, J. Amer. Math. Soc. 19 (2006), no. 2, 447–459. MR 2188132, DOI 10.1090/S0894-0347-05-00506-0
- J. M. Landsberg, Tensors: geometry and applications, Graduate Studies in Mathematics, vol. 128, American Mathematical Society, Providence, RI, 2012. MR 2865915, DOI 10.1090/gsm/128
- J. M. Landsberg, Geometry and complexity theory, Cambridge Studies in Advanced Mathematics, vol. 169, Cambridge University Press, Cambridge, 2017. MR 3729273, DOI 10.1017/9781108183192
- J. M. Landsberg and Mateusz Michałek, Abelian tensors, J. Math. Pures Appl. (9) 108 (2017), no. 3, 333–371 (English, with English and French summaries). MR 3682743, DOI 10.1016/j.matpur.2016.11.004
- J. M Landsberg and M. Michałek, A lower bound for the border rank of matrix multiplication, IMRN, 15 (2018), 4722–4733.
- J. M. Landsberg and Mateusz Michałek, On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry, SIAM J. Appl. Algebra Geom. 1 (2017), no. 1, 2–19. MR 3633766, DOI 10.1137/16M1067457
- Joseph M. Landsberg and Giorgio Ottaviani, New lower bounds for the border rank of matrix multiplication, Theory Comput. 11 (2015), 285–298. MR 3376667, DOI 10.4086/toc.2015.v011a011
- R. P. Laudone. Syzygies of secant ideals of Plücker-embedded Grassmannians are generated in bounded degree, arXiv:1803.04259 (2018).
- François Le Gall, Powers of tensors and fast matrix multiplication, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 296–303. MR 3239939, DOI 10.1145/2608628.2608664
- Ketan D. Mulmuley and Milind Sohoni, Geometric complexity theory. I. An approach to the P vs. NP and related problems, SIAM J. Comput. 31 (2001), no. 2, 496–526. MR 1861288, DOI 10.1137/S009753970038715X
- Steven V. Sam, Ideals of bounded rank symmetric tensors are generated in bounded degree, Invent. Math. 207 (2017), no. 1, 1–21. MR 3592755, DOI 10.1007/s00222-016-0668-2
- Tim Seynnaeve, Plethysm and fast matrix multiplication, C. R. Math. Acad. Sci. Paris 356 (2018), no. 1, 52–55 (English, with English and French summaries). MR 3754619, DOI 10.1016/j.crma.2017.11.012
- Yaroslav Shitov, A counterexample to Comon’s conjecture, SIAM J. Appl. Algebra Geom. 2 (2018), no. 3, 428–443. MR 3852707, DOI 10.1137/17M1131970
- Y. Shitov, A counterexample to strassen’s direct sum conjecture, arXiv:1712.08660 (2017).
- A. V. Smirnov, The bilinear complexity and practical algorithms for matrix multiplication, Zh. Vychisl. Mat. Mat. Fiz. 53 (2013), no. 12, 1970–1984 (Russian, with Russian summary); English transl., Comput. Math. Math. Phys. 53 (2013), no. 12, 1781–1795. MR 3146566, DOI 10.1134/S0965542513120129
- Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
- Volker Strassen, Vermeidung von Divisionen, J. Reine Angew. Math. 264 (1973), 184–202 (German, with English summary). MR 521168
- L. G. Valiant, Completeness classes in algebra, Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979) ACM, New York, 1979, pp. 249–261. MR 564634
- Virginia Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd [extended abstract], STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887–898. MR 2961552, DOI 10.1145/2213977.2214056
- S. Winograd, On multiplication of $2\times 2$ matrices, Linear Algebra Appl. 4 (1971), 381–388. MR 297115, DOI 10.1016/0024-3795(71)90009-7
Reviewer information
Additional Information
- Journal: Bull. Amer. Math. Soc. 57 (2020), 317-324
- DOI: https://doi.org/10.1090/bull/1661
- Published electronically: December 3, 2018
- Review Copyright: © Copyright 2018 American Mathematical Society