Accelerating Sampling Algorithms via Domain Sparsification

Suppose that we are given oracle access to a distribution over subsets of size k from a ground set of n elements, and our goal is to generate approximate samples from the distribution. Many discrete sampling tasks can be reduced to this canonical form, and in many cases the size n of the ground set is much larger than the size k of the sampled set. A natural question arises: When can we sample from the distribution in time sublinear in the ground set size n? In general this is impossible, since we must observe all elements of the ground set to know where the distribution mass is concentrated. Yet, it turns out that for a large class of discrete distributions, after some initial preprocessing, we can sample in time not only sublinear, but completely independent of n, and merely polynomial in the target sample size k. This is possible thanks to domain sparsification, a framework for reducing the task of sampling over a ground set of n elements to sampling over a drastically smaller ground set. I will survey this emerging line of works, from its beginnings studying the complexity of sampling determinantal point processes, to extensions such as counting the bases of a matroid, and finally, recent efforts to provide a complete characterization of distributions that admit domain sparsification schemes.