An efficient tree decomposition method for permanents and mixed discriminants

Abstract

We present an efficient algorithm to compute permanents, mixed discriminants and hyperdeterminants of structured matrices and multidimensional arrays (tensors). We describe the sparsity structure of an array in terms of a graph, and we assume that its treewidth, denoted as $\omega$, is small. Our algorithm requires $O(n{2}^{\omega })$ arithmetic operations to compute permanents, and $O(n^2+n{3}^{\omega })$ for mixed discriminants and hyperdeterminants. We finally show that mixed volume computation continues to be hard under bounded treewidth assumptions.

32 pages, 4 figures

References in corpus (3)

• Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
• Unifying two Graph Decompositions with Modular Decomposition
• Efficient Computation of the Permanent of Block Factorizable Matrices

Cited by in corpus (10)

• Classical simulation of boson sampling based on graph structure
• Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
• Efficient computation of permanents, with applications to boson sampling and random matrices
• Chordal networks of polynomial ideals
• Monitoring-induced Entanglement Entropy and Sampling Complexity
• Exact recursive calculation of circulant permanents: A band of different diagonals inside a uniform matrix
• On the Parameterized Intractability of Determinant Maximization
• Approximating outcome probabilities of linear optical circuits
• A duality at the heart of Gaussian boson sampling
• On the Complexity of Toric Ideals