# Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes

arXiv: https://arxiv.org/abs/2111.14148 · HTML: https://mlsanity.com/paper/2111.14148/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 72 references that are in the map.
- First posted on arXiv 28 Nov 2021.

## Builds on (most cited first, 16 of 16)

- [Fair and Diverse DPP-based Data Summarization](https://mlsanity.com/paper/1802.04023/) (2018)
- [Learning the Parameters of Determinantal Point Process Kernels](https://mlsanity.com/paper/1402.4862/) (2014)
- [Learning Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/1905.12962/) (2019)
- [Fast DPP Sampling for Nystr"om with Application to Kernel Methods](https://mlsanity.com/paper/1603.06052/) (2016)
- [Low-Rank Factorization of Determinantal Point Processes for Recommendation](https://mlsanity.com/paper/1602.05436/) (2016)
- [Randomized Rounding for the Largest Simplex Problem](https://mlsanity.com/paper/1412.0036/) (2014)
- [Parameterized Algorithms for the Matrix Completion Problem](https://mlsanity.com/paper/1804.03423/) (2018)
- [Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid](https://mlsanity.com/paper/1811.01816/) (2018)
- [On largest volume simplices and sub-determinants](https://mlsanity.com/paper/1406.3512/) (2014)
- [Flexible Modeling of Diversity with Strongly Log-Concave Distributions](https://mlsanity.com/paper/1906.05413/) (2019)
- [On the Complexity of Constrained Determinantal Point Processes](https://mlsanity.com/paper/1608.00554/) (2016)
- [Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes](https://mlsanity.com/paper/2109.00727/) (2021)
- [Block-Wise MAP Inference for Determinantal Point Processes with Application to Change-Point Detection](https://mlsanity.com/paper/1503.06239/) (2015)
- [A Generalization of Permanent Inequalities and Applications in Counting and Optimization](https://mlsanity.com/paper/1702.02937/) (2017)
- [Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts](https://mlsanity.com/paper/1407.2929/) (2014)
- [Spanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate](https://mlsanity.com/paper/2102.12646/) (2021)

## Abstract (arXiv)

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 complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: (1) Computing sumSdet(bf AS,S)p exactly for every (fixed) positive even integer p is UP-hard and Mod3P-hard, which gives a negative answer to an open question posed by Kulesza and Taskar. (2) sumSdet(bf AS,S)det(bf BS,S)det(bf CS,S) is NP-hard to approximate within a factor of 2^O(|I|1-ε) or 2^O(n1/ε) for any ε>0, where |I| is the input size and n is the order of the input matrix. This result is stronger than the #P-hardness for the case of two matrices derived by Gillenwater. (3) There exists a kO(k)nO(1)-time algorithm for computing sumSdet(bf AS,S)det(bf BS,S), where k is the maximum rank of bf A and bf B or the treewidth of the graph formed by nonzero entries of bf A and bf B. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix bf A of treewidth w: (4) We can compute a 2^fracn2p-1-approximation to sumSdet(bf AS,S)p for any fractional number p>1 in wO(wp)nO(1) time. (5) We can find a 2√ n-approximation to unconstrained MAP inference in wO(w√ n)nO(1) time.