# An efficient tree decomposition method for permanents and mixed discriminants

Published in *Linear Algebra and its Applications*, 2016

Recommended citation: Diego Cifuentes, Pablo Parrilo (2016). "An efficient tree decomposition method for permanents and mixed discriminants." *Linear Algebra and its Applications*. 493:45-81. __http://dx.doi.org/10.1016/j.laa.2015.12.004__

We present an efficient algorithm to compute permanents, mixed discriminants and hyperdeterminants of structured matrices and multidimensional arrays.
We describe the sparsity structure of an array in terms of a graph, and we assume that its treewidth *ω* is small.
Our algorithm requires *O(n 2^ω)* operations to compute permanents, and *O(n^2 + n 3^ω)* for mixed discriminants and hyperdeterminants.
Mixed volume computation remains NP-hard for bounded treewidth.

See also:

- My slides from SIAM Conference on Discrete Mathematics’ 16
- My Matlab code