On the (In)tractability of Computing Normalizing Constants for the Product of Determinantal Point Processes

We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant, which is among the most essential probabilistic inference tasks. Our complexitytheoretic results (almost) rule out the existence of efficient algorithms for this task, unless input matrices are forced to have favorable structures. In particular, we prove the following:

(1) Computing S det(A S,S ) p exactly for every (fixed) positive even integer p is UP-hard and Mod 3 P-hard, which gives a negative answer to an open question posed by Kulesza & Taskar (2012).

(2) S det(A S,S ) det(B S,S ) det(C S,S ) is NPhard to approximate within a factor of 2 O(|I| 1-) for any > 0, where |I| is the input size. This result is stronger than #P-hardness for the case of two matrices by Gillenwater ( 2014).

(3) There exists a k O(k) |I| O(1) -time algorithm for computing S det(A S,S ) det(B S,S ), where k is "the maximum rank of A and B" or "the treewidth of the graph induced by nonzero entries of A and B." Such parameterized algorithms are said to be fixed-parameter tractable.