ON-LINE QLunch: Radu Curticapean

Speaker: Radu Curticapean

Title: The complexity of immanants

Abstract: Immanants are matrix functionals that generalize determinants and permanents. Given an irreducible character χ_λ of S_n for some partition λ of n, the immanant associated with λ is a sum-product over permutations π in S_n, much like the determinant, but with χ_λ(π) playing the role of sgn(π).

Hartmann showed in 1985 that immanants can be evaluated in polynomial time for sign-ish characters. More precisely, for a partition λ of n with s parts, let b(λ) := n−s count the boxes to the right of the first column in the Young diagram of λ. The immanant associated with λ can be evaluated in n^O(b(λ)) time.

Since this initial result, complementing hardness results have been obtained for several families of immanants derived from partitions with unbounded b(λ). This includes permanents, immanants associated with hook characters, and other classes. In this talk, we complete the picture of hard immanant families: Under a standard assumption from parameterized complexity, we rule out polynomial-time algorithms for (well-behaved) immanant families with unbounded b(λ). For immanant families in which b(λ) even grows polynomially, we establish hardness for #P and VNP.

Link to paper:

https://arxiv.org/abs/2102.04340

Bio:
Radu is an assistant professor at the IT University of Copenhagen, co-affiliated with Basic Algorithms Research Copenhagen. He graduated at Saarland University (Germany) in 2015 and later held post-doc positions at the Hungarian Academy of Sciences in Budapest, the Simons Institute for the Theory of Computing at UC Berkeley, and BARC/ITU in Copenhagen. His work focuses on the computational complexity of counting problems, fixed-parameter tractability, and algebraic methods for algorithms and complexity.

Join Zoom Meeting:
https://ucph-ku.zoom.us/j/67743681357