Geometric complexity theory and matrix powering

DOI10.1016/J.DIFGEO.2017.07.001MaRDI QIDQ1679673zbMATH OpenOpenAlexWikidataFDO

Authors Fulvio Gesmundo, Christian Ikenmeyer, Greta Panova

Publication date 21 November 2017

Published in Differential Geometry and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.00827

zbMATH Keywords

geometric complexity theorymatrix poweringsymmetric Kronecker coefficients

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Determinants, permanents, traces, other special matrix functions (15A15) Representations of finite symmetric groups (20C30)

Abstract: Valiant's famous determinant versus permanent problem is the flagship problem in algebraic complexity theory. Mulmuley and Sohoni (Siam J Comput 2001, 2008) introduced geometric complexity theory, an approach to study this and related problems via algebraic geometry and representation theory. Their approach works by multiplying the permanent polynomial with a high power of a linear form (a process called padding) and then comparing the orbit closures of the determinant and the padded permanent. This padding was recently used heavily to show no-go results for the method of shifted partial derivatives (Efremenko, Landsberg, Schenck, Weyman, 2016) and for geometric complexity theory (Ikenmeyer Panova, FOCS 2016 and B"urgisser, Ikenmeyer Panova, FOCS 2016). Following a classical homogenization result of Nisan (STOC 1991) we replace the determinant in geometric complexity theory with the trace of a variable matrix power. This gives an equivalent but much cleaner homogeneous formulation of geometric complexity theory in which the padding is removed. This radically changes the representation theoretic questions involved to prove complexity lower bounds. We prove that in this homogeneous formulation there are no orbit occurrence obstructions that prove even superlinear lower bounds on the complexity of the permanent. This is the first no-go result in geometric complexity theory that rules out superlinear lower bounds in some model. Interestingly---in contrast to the determinant---the trace of a variable matrix power is not uniquely determined by its stabilizer.

Recommendations

• No occurrence obstructions in geometric complexity theory
• Padded polynomials, their cousins, and geometric complexity theory
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Geometric complexity theory and tensor rank
• On geometric complexity theory: multiplicity obstructions are stronger than occurrence obstructions

Cites work

• scientific article; zbMATH DE number 1001729 (Why is no real title available?)
• scientific article; zbMATH DE number 44019 (Why is no real title available?)
• scientific article; zbMATH DE number 51906 (Why is no real title available?)
• scientific article; zbMATH DE number 1503622 (Why is no real title available?)
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• scientific article; zbMATH DE number 3350172 (Why is no real title available?)
• An overview of mathematical issues arising in the geometric complexity theory approach to \(\mathbf{VP}\neq\mathbf{VNP}\)
• Characterizing Valiant's algebraic complexity classes
• Characters of the Weyl group of SU(n) on zero weight spaces and centralizers of permutation representations
• Fundamental invariants of orbit closures
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Geometric aspects of iterated matrix multiplication
• Geometric complexity theory and tensor rank
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Lie Groups, Lie Algebras, and Representations
• Lie groups. An approach through invariants and representations
• Linear Preserver Problems
• On the complexity of the permanent in various computational models
• Padded polynomials, their cousins, and geometric complexity theory
• Strict unimodality of \(q\)-binomial coefficients
• Symmetry, Representations, and Invariants
• The method of shifted partial derivatives cannot separate the permanent from the determinant

Cited in

(16)

• On the complexity of the permanent in various computational models
• An introduction to geometric complexity theory
• Geometric complexity theory and tensor rank
• The classification of multiplicity-free plethysms of Schur functions
• scientific article; zbMATH DE number 7561749 (Why is no real title available?)
• A Rank 18 Waring Decomposition of sM_〈3〉 with 432 Symmetries
• Rank and border rank of Kronecker powers of tensors and Strassen's laser method
• Complexity of linear circuits and geometry
• Padded polynomials, their cousins, and geometric complexity theory
• On geometric complexity theory: multiplicity obstructions are stronger than occurrence obstructions
• Fundamental invariants of orbit closures
• scientific article; zbMATH DE number 7559443 (Why is no real title available?)
• Splitting Kronecker squares, 2-decomposition numbers, Catalan combinatorics, and the Saxl conjecture
• Unifying known lower bounds via geometric complexity theory
• scientific article; zbMATH DE number 4137244 (Why is no real title available?)
• No occurrence obstructions in geometric complexity theory

Describes a project that uses

Uses Software

• lowerbounds-survey

This page was built for publication: Geometric complexity theory and matrix powering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679673)