Constrained Bombieri Point Processes

Determinantal point processes allow efficient sampling of diverse subsets of data. However, (exact) sampling under additional constraints is often computationally intractable under complexity-theoretic assumptions. We take an algebraic approach to designing novel algorithms that allow exact constrained sampling with theoretical efficiency guarantees. Our algorithms apply to a general class of point processes based on Bombieri inner products of polynomials, which we call Bombieri $k$-point processes. This perspective recovers known algorithms for constrained $k$-DPPs and extends them to a broader class of simple $k$-point processes. As applications, we obtain exact samplers for matching-, path-, subgraph-, and budget-constrained processes, as well as distributions combining diversity with clustering. While common complexity-theoretic assumptions rule out polynomial-time algorithms in many of these settings, our algorithms are efficient with respect to the relaxed notion of fixed-parameter tractability when the sample size $k$ is kept bounded.