Geometric complexity theory and matrix powering

DOI10.1016/J.DIFGEO.2017.07.001zbMATH Open1390.68320arXiv1611.00827OpenAlexW2547332850WikidataQ115355354 ScholiaQ115355354MaRDI QIDQ1679673FDOQ1679673

Greta Panova, Fulvio Gesmundo, Christian Ikenmeyer

Publication date: 21 November 2017

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

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.

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

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

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)

Cites Work

• Lie groups. An approach through invariants and representations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Symmetry, Representations, and Invariants
• Linear Preserver Problems
• Characterizing Valiant's algebraic complexity classes
• Title not available (Why is that?)
• Geometric complexity theory and tensor rank
• Geometric aspects of iterated matrix multiplication
• An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Strict unimodality of \(q\)-binomial coefficients
• Title not available (Why is that?)
• Title not available (Why is that?)
• The method of shifted partial derivatives cannot separate the permanent from the determinant
• Fundamental invariants of orbit closures
• Title not available (Why is that?)
• Lie Groups, Lie Algebras, and Representations
• Characters of the Weyl group of SU(n) on zero weight spaces and centralizers of permutation representations
• On the complexity of the permanent in various computational models
• Padded Polynomials, Their Cousins, and Geometric Complexity Theory

Cited In (11)

• Title not available (Why is that?)
• Rank and border rank of Kronecker powers of tensors and Strassen's laser method
• Complexity of linear circuits and geometry
• Splitting Kronecker squares, 2-decomposition numbers, Catalan combinatorics, and the Saxl conjecture
• An introduction to geometric complexity theory
• Title not available (Why is that?)
• The classification of multiplicity-free plethysms of Schur functions
• A Rank 18 Waring Decomposition of sM_〈3〉 with 432 Symmetries
• On the complexity of the permanent in various computational models
• No occurrence obstructions in geometric complexity theory
• Title not available (Why is that?)

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)