Spanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate
This work addresses a theoretical computational problem for researchers in machine learning and graph theory, showing incremental hardness results for constrained DPPs.
The paper tackles the computational hardness of evaluating the normalizing constant for determinantal point processes constrained by spanning trees, proving it is #P-hard and providing approximation-preserving reductions from problems without known efficient approximations.
We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph $G=(V,E)$ and a positive semi-definite matrix $\mathbf{A}$ indexed by $E$, a spanning-tree DPP defines a distribution such that we draw $S\subseteq E$ with probability proportional to $\det(\mathbf{A}_S)$ only if $S$ induces a spanning tree. We prove $\sharp\textsf{P}$-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.