Permanent versus determinant, obstructions, and Kronecker coefficients

MaRDI QIDQ726486zbMATH OpenFDO

Authors Peter Bürgisser

Publication date 11 July 2016

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.08113, http://www.emis.de/journals/SLC/wpapers/s75buerg.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

representationsYoung tableauxgeometric complexity theoryorbit closuresKronecker coefficientsplethysmshighest weight vectorspermanent versus determinant

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of representation theory (05E10) Representations of finite symmetric groups (20C30)

Abstract: We give an introduction to some of the recent ideas that go under the name "geometric complexity theory". We first sketch the proof of the known upper and lower bounds for the determinantal complexity of the permanent. We then introduce the concept of a representation theoretic obstruction, which has close links to algebraic combinatorics, and we explain some of the insights gained so far. In particular, we address very recent insights on the complexity of testing the positivity of Kronecker coefficients. We also briefly discuss the related asymptotic version of this question.

Recommendations

• A generalization of permanents and determinants
• Permanents, determinants, and generalized complementary basic matrices
• Matrix factorizations of determinants and permanents
• Permanent versus determinant over a finite field
• Permanent analogues of determinantal identities related to permutation fixed-points
• Determinant, permanent, and MacMahon's master theorem
• Permanents and determinants with generic noncommuting entries
• On two determinantal identities and their permanent analogues
• On the Relation Between the Determinant and the Permanent on Symmetric Matrices
• Approximating the permanent via nonabelian determinants

Cited in

(10)

• Permanent analogues of determinantal identities related to permutation fixed-points
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• On the largest Kronecker and Littlewood-Richardson coefficients
• On vanishing of Kronecker coefficients
• Improved construction for universality of determinant and permanent
• scientific article; zbMATH DE number 5057518 (Why is no real title available?)
• Obstructions to determinantal representability
• A determinantal identity for the permanent of a rank 2 matrix
• On the Pólya conversion problem for permanents and determinants
• Permanents, Determinants, Weighted Isobaric Polynomials and Integer Sequences

This page was built for publication: Permanent versus determinant, obstructions, and Kronecker coefficients

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