Permanent versus determinant, obstructions, and Kronecker coefficients

zbMATH Open1362.68089arXiv1511.08113MaRDI QIDQ726486FDOQ726486

Peter Bürgisser

Publication date: 11 July 2016

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

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.

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

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

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

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)

Cited In (10)

• A Determinantal Identity for the Permanent of a Rank 2 Matrix
• 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
• Title not available (Why is that?)
• Obstructions to determinantal representability
• On the Pólya conversion problem for permanents and determinants
• Permanents, Determinants, Weighted Isobaric Polynomials and Integer Sequences
• Permanent analogues of determinantal identities related to permutation fixed-points

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)