
Graduate Surveys 10
Abstract: [Plain Text Version]
Geometric complexity theory is an approach towards proving lower bounds in algebraic complexity theory via methods from algebraic geometry and representation theory. It was introduced by Mulmuley and Sohoni and has gained significant momentum over the last few years. Since deep methods from several different areas of mathematics are involved, geometric complexity theory has a steep learning curve. There are great survey articles on geometric complexity theory, but those require a significant level of mathematical background or often only sketch many of the proofs, see, e.g., Regan (Bull. EATCS 2002), Mulmuley (J. ACM 2011), Bürgisser, Landsberg, Manivel, Weyman (SIAM J. Comput. 2011), Grochow (PhD thesis, U. of Chicago 2012), Ikenmeyer (PhD thesis, Paderborn U., 2012), Landsberg (Ann. U. di Ferrara, 2015). This survey tries to be a gentle introduction for graduate students and even advanced undergraduate students in computer science that requires almost no background knowledge except for the usual knowledge in linear algebra and some basic knowledge in analysis. All the necessary concepts from algebraic geometry and representation theory are introduced and almost all proofs are given. We focus on two questions, the permanent versus determinant problem and the border rank problem for matrix multiplication. There have been many more results in the past few years, which we cannot cover, however, this survey should give the reader the neccessary background to understand them. The survey culminates in two recent results, a negative one for the permanent versus determinant question and a positive one for the matrix multiplication problem. We present the proof that occurrence obstructions essentially cannot resolve the permanent versus determinant question. However, occurence obstructions are only the most basic tool of geometric complexity theory and it might be well possible that the more general concept of multiplicity obstructions will resolve the problem. On the other hand, as a proof of concept, we show that occurrence obstructions indeed can give lower bounds for the border rank of matrix multiplication.