Geometric complexity theory: an introduction for geometers

Agrawal, M., Vinay, V.: Arithmetic circuits: a chasm at depth four. In: Proceedings of the 49th IEEE symposium on foundations of computer science, pp. 6775 (2008)

Alon, N., Tarsi, M.: Colorings and orientations of graphs. Combinatorica 12(2), 125–134 (1992)

Beauville, A.: Determinantal hypersurfaces. Michigan Math. J. 48, 39–64. Dedicated to William Fulton on the occasion of his 60th birthday (2000)

Ben Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. SIAM J. Comput. 21(21), 54–58 (1992)

Brent, R.P.: The parallel evaluation of general arithmetic expressions. J. Assoc. Comput. Mach. 21, 201–206 (1974)

Briand, E.: Polynômes multisymétriques, Ph.D. thesis, Université de Rennes 1 et Universidad de Cantabria (2002)

Briand, E.: Covariants vanishing on totally decomposable forms. In: Alonso, M.E., Arrondo, E., Mallavibarrena, R., Sols, I. (eds.) Liaison, Schottky problem and invariant theory, Progr. Math., vol. 280, pp. 237–256. Birkhäuser Verlag, Basel (2010)

Brion, M.: Stable properties of plethysm: on two conjectures of Foulkes. Manuscripta Math. 80(4), 347–371 (1993)

Brion, M.: Sur certains modules gradués associés aux produits symétriques, Algèbre non commutative, groupes quantiques et invariants (Reims, 1995), Sémin. Congr., vol. 2, Soc. Math. France, Paris, pp. 157–183 (1997)

Bürgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic complexity theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315. Springer-Verlag, Berlin, With the collaboration of Thomas Lickteig (1997)

Bürgisser, P., Ikenmeyer, C.: Geometric complexity theory and tensor rank [extended abstract], STOC’11—Proceedings of the 43rd ACM symposium on theory of computing, pp. 509–518. ACM, New York (2011)

Bürgisser, P., Landsberg, J.M., Manivel, L., Weyman, J.: An overview of mathematical issues arising in the geometric complexity theory approach to $${\rm VP}\ne {\rm VNP}$$ VP ≠ VNP . SIAM J. Comput. 40(4), 1179–1209 (2011)

Caracciolo, S., Sokal, A.D., Sportiello, A.: Algebraic/combinatorial proofs of Cayley-type identities for derivatives of determinants and pfaffians. Adv. Appl. Math. 50(4), 474–594 (2013)

Chen, X., Kayal, N., Wigderson, A.: Partial derivatives in arithmetic complexity and beyond, Found. Trends Theor. Comput. Sci. 6(1–2), front matter, 1–138 (2011) (2010)

Dieudonné, J.: Sur une généralisation du groupe orthogonal à quatre variables. Arch. Math. 1, 282–287 (1949)

Dolgachev, I.: Lectures on Invariant Theory, London Mathematical Society Lecture Note Series, vol. 296. Cambridge University Press, Cambridge (2003)

Drisko, A.A.: On the number of even and odd Latin squares of order $$p+1$$ p + 1 . Adv. Math. 128(1), 20–35 (1997)

Efremenko, K., Landsberg, J.M., Schenck, H.: Shifted partials, young flattenings, and other equations in complexity theory (in preparation)

Eisenbud, D.: Commutative Algebra, Graduate Texts In Mathematics, vol. 150. Springer-Verlag, New York, With a view toward algebraic geometry (1995)

Fischer, I.: Sums of like powers of multivariate linear forms. Math. Mag. 67(1), 59–61 (1994)

Foulkes, H.O.: Concomitants of the quintic and sextic up to degree four in the coefficients of the ground form. J. Lond. Math. Soc. 25, 205–209 (1950)

Frobenius, G.: Über die Darstellung der endlichen Gruppen durch lineare Substitutionen, pp. 994–1015. Sitzungsber Deutsch. Akad. Wiss., Berlin (1897)

Fulton, W.: Young Tableaux, London Mathematical Society Student Texts, vol. 35. Cambridge University Press, Cambridge, With applications to representation theory and geometry (1997)

Fulton, W., Harris, J.: Representation Theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, A first course, Readings in Mathematics (1991)

Garibaldi, S., Guralnick, R.: Simple algebraic groups are (usually) determined by an invariant, arXiv:1309.6611 (2013)

Gay, D.A.: Characters of the Weyl group of $$SU(n)$$ S U ( n ) on zero weight spaces and centralizers of permutation representations, Rocky Mountain. J. Math. 6(3), 449–455 (1976)

Gel’fand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants, Resultants, and Multidimensional Determinants, Mathematics: Theory & Applications. Birkhäuser Boston Inc., Boston, MA (1994)

Gesmundo, F., Hauenstein, J, Ikenmeyer, C., Landsberg, J.M.: Geometry and matrix rigidity. arXiv:1310.1362

Glynn, D.G.: The conjectures of Alon-Tarsi and Rota in dimension prime minus one. SIAM J. Discret. Math. 24(2), 394–399 (2010)

Grenet, B.: An Upper Bound for the Permanent versus Determinant Problem, Manuscript (submitted). http://www.lix.polytechnique.fr/~grenet/publis/Gre11.pdf (2011)

Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Arithmetic circuits: a chasm at depth three. Electron. Colloquium Comput. Complex. (ECCC) 20, 26 (2013)

Gurvits, L.: Ryser (or polarization) formula for the permanent is essentially optimal: the waring rank approach, preprint

Hadamard, J.: Mémoire sur l’élimination. Acta Math. 20(1), 201–238 (1897)

Hadamard, J.: Sur les conditions de décomposition des formes. Bull. Soc. Math. France 27, 34–47 (1899)

Hermite, C.: Sur la theorie des fonctions homogenes a deux indeterminees. Camb. Dublin Math. J. 9, 172–217 (1854)

Howe, R.: $$({\rm GL}_n,{\rm GL}_m)$$ ( GL n , GL m ) -duality and symmetric plethysm. Proc. Indian Acad. Sci. Math. Sci. 97(1—-3), 85–109 (1987)

Huang, R., Rota, G.-C.: On the relations of various conjectures on Latin squares and straightening coefficients. Discret. Math. 128(1—-3), 225–236 (1994)

Ikenmeyer, C.: Geometric complexity theory, tensor rank, and Littlewood-Richardson coefficients, Ph.D. thesis, Institute of Mathematics, University of Paderborn, Available at http://math-www.uni-paderborn.de/agpb/work/ikenmeyer_thesis.pdf (2012)

Kadish, H., Landsberg, J.M.: Padded polynomials, their cousins, and geometric complexity theory. Comm. Algebra 42(5), 2171–2180 (2014)

Koiran, P.: Arithmetic circuits: the chasm at depth four gets wider, Theor. Comput. Sci. 448, 56–65. doi: 10.1016/j.tcs.2012.03.041 (2012)

Kumar, A., Lokam, S.V., Patankar, V.M., 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, pp. 299–310 (2009)

Kumar, S.: A study of the representations supported by the orbit closure of the determinant. arXiv:1109.5996

Kumar, S.: Geometry of orbits of permanents and determinants. Comment. Math. Helv. 88(3), 759–788 (2013)

Landsberg, J.M.: $$P$$ P versus $$NP$$ N P and geometry. J. Symbolic Comput. 45(12), 1369–1377 (2010)

Landsberg, J.M.: Tensors: Geometry and Applications, Graduate Studies in Mathematics, vol. 128. American Mathematical Society, Providence, RI (2012)

Landsberg, J.M., Ottaviani, G.: Equations for secant varieties of Veronese and other varieties. Ann. Mat. Pura Appl. 192(4), 569–606 (2013)

Landsberg, J.M., Weyman, J.: On the ideals and singularities of secant varieties of Segre varieties. Bull. Lond. Math. Soc. 39(4), 685–697 (2007)

Landsberg, J.M., Ottaviani, G.: New lower bounds for the border rank of matrix multiplication, preprint. arXiv:1112.6007

Landsberg, J.M., Manivel, L., Ressayre, N.: Hypersurfaces with degenerate duals and the geometric complexity theory program. Comment. Math. Helv. 88(2), 469–484 (2013)

Malod, G., Portier, N.: Characterizing Valiant’s algebraic complexity classes. J. Complex. 24, 16–38 (2008)

Manivel, L.: Gaussian maps and plethysm, Algebraic geometry (Catania, 1993/Barcelona, 1994), Lecture Notes in Pure and Appl. Math., vol. 200, pp. 91–117. Dekker, New York, (1998)

Marcus, M., May, F.C.: The permanent function. Canad. J. Math. 14, 177–189 (1962)

Massarenti, A., Raviolo, E.: The rank of $$n\times n$$ n × n matrix multiplication is at least $$3n^2-2\sqrt{2}n^\frac{3}{2}-3n$$ 3 n 2 - 2 2 n 3 2 - 3 n . Linear Algebra Appl. 438(11), 4500–4509 (2013)

Matsushima, Y.: Espaces homogènes de Stein des groupes de Lie complexes. Nagoya Math. J 16, 205–218 (1960)

Maulik, D., Pandharipande, R.: Gromov-Witten theory and Noether-Lefschetz theory. In: A celebration of algebraic geometry. Clay Math. Proc., vol. 18, pp. 469–507. American Mathematical Society (2013)

McKay, T.: On plethysm conjectures of Stanley and Foulkes. J. Algebra 319(5), 2050–2071 (2008)

Mignon, T., Ressayre, N.: A quadratic bound for the determinant and permanent problem. Int. Math. Res. Not. 79, 4241–4253 (2004)

Müller, J., Neunhöffer, M.: Some computations regarding Foulkes’ conjecture. Exp. Math. 14(3), 277–283 (2005)

Mulmuley, K.: Geometric complexity theory vii: nonstandard quantum group for the plethysm problem. arXiv:0709.0749

Mulmuley, K.: Geometric complexity theory viii: on canonical bases for the nonstandard quantum groups. arXiv:0709.0751

Mulmuley, K.D., Narayanan, H., Sohoni, M.: Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebraic Combin. 36(1), 103–110 (2012)

Mulmuley, K.D., Sohoni, M.: Geometric complexity theory. I. An approach to the P vs. NP and related problems. SIAM J. Comput. 31(2), 496–526 (2001). (electronic)

Mulmuley, K.D., Sohoni, M.: Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties. SIAM J. Comput. 38(3), 1175–1206 (2008)

Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. Comput. Complex. 6(3), 217–234 (1996/1997)

Popov, V.L.: Two orbits: when is one in the closure of the other?, Tr. Mat. Inst. Steklova 264, no. Mnogomernaya Algebraicheskaya Geometriya, 152–164 (2009)

Procesi, C.: Lie groups, Universitext. Springer, New York, An approach through invariants and representations (2007)

Ranestad, K., Schreyer, F.-O.: On the rank of a symmetric form. J. Algebra 346, 340–342 (2011)

Segre, B.: Bertini forms and Hessian matrices. J. Lond. Math. Soc. 26, 164–176 (1951)

Shafarevich, I.R.: Basic algebraic geometry. 1, second ed., Springer-Verlag, Berlin, Varieties in projective space, Translated from the 1988 Russian edition and with notes by Miles Reid (1994)

Shpilka, A., Wigderson, A.: Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complex. 10(1), 1–27 (2001)

Sipser, M.: The history and status of the p versus np question. In: STOC ’92 proceedings of the 24th annual ACM symposium on theory of computing, pp. 603–618 (1992)

Strassen, V.: Die Berechnungskomplexität der symbolischen Differentiation von Interpolationspolynomen. Theor. Comput. Sci. 1(1), 21–25 (1975)

Tavenas, S.: Improved bounds for reduction to depth 4 and depth 3, preprint arXiv:1304.5777

Valiant, L.G., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12(4), 641–644 (1983)

Valiant, L.G.: Completeness classes in algebra. In: Proceedings of the 11th ACM STOC, pp. 249–261 (1979)

Wahl, J.: Gaussian maps and tensor products of irreducible representations. Manuscripta Math. 73(3), 229–259 (1991)

Weyl, H.: The Classical Groups, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, Their invariants and representations, 15th printing, Princeton Paperbacks (1997)

Ye, K.: The stabilizer of immanants. Linear Algebra Appl. 435(5), 1085–1098 (2011)