# Spanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 29 references that are in the map.
- First posted on arXiv 25 Feb 2021.

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

- [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)
- [On the Complexity of Constrained Determinantal Point Processes](https://mlsanity.com/paper/1608.00554/) (2016)

## Built on by (most cited first, 1 of 1)

- [Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes](https://mlsanity.com/paper/2111.14148/) (2021)

## Abstract (arXiv)

We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph G=(V,E) and a positive semi-definite matrix A indexed by E, a spanning-tree DPP defines a distribution such that we draw Ssubseteq E with probability proportional to det(AS) only if S induces a spanning tree. We prove sharptextsfP-hardness of computing the normalizing constant for spanning-tree DPPs and provide an approximation-preserving reduction from the mixed discriminant, for which FPRAS is not known. We show similar results for DPPs constrained by forests.