STOC2021

A full complexity dichotomy for immanant families

Radu Curticapean

1 citation

Abstract

Given an integer n ≥ 1 and an irreducible character χλ of Sn for some partition λ of n, the immanant immλ:ℂn× n→ℂ maps matrices A∈ℂn× n to immλ(A)=∑π∈ Snχλ(π)∏i=1nAi,π(i). Important special cases include the determinant and permanent, which are obtained from the sign and trivial character, respectively.