Testing Determinantal Point Processes
  Determinantal point processes (DPPs) are popular probabilistic models of
diversity. In this paper, we investigate DPPs from a new perspective: property
testing of distributions. Given sample access to an unknown distribution $q$
over the subsets of a ground set, we aim to distinguish whether $q$ is a DPP
distribution, or $\epsilon$-far from all DPP distributions in
$\ell_1$-distance. In this work, we propose the first algorithm for testing
DPPs. Furthermore, we establish a matching lower bound on the sample complexity
of DPP testing. This lower bound also extends to showing a new hardness result
for the problem of testing the more general class of log-submodular
distributions.
