Yang P. Liu

Nima Anari, Yang P. Liu, Thuy-Duong Vuong

We design fast algorithms for repeatedly sampling from strongly Rayleigh distributions, which include random spanning tree distributions and determinantal point processes. For a graph $G=(V, E)$, we show how to approximately sample uniformly random spanning trees from $G$ in $\widetilde{O}(\lvert V\rvert)$ time per sample after an initial $\widetilde{O}(\lvert E\rvert)$ time preprocessing. For a determinantal point process on subsets of size $k$ of a ground set of $n$ elements, we show how to approximately sample in $\widetilde{O}(k^ω)$ time after an initial $\widetilde{O}(nk^{ω-1})$ time preprocessing, where $ω<2.372864$ is the matrix multiplication exponent. We even improve the state of the art for obtaining a single sample from determinantal point processes, from the prior runtime of $\widetilde{O}(\min\{nk^2, n^ω\})$ to $\widetilde{O}(nk^{ω-1})$. In our main technical result, we achieve the optimal limit on domain sparsification for strongly Rayleigh distributions. In domain sparsification, sampling from a distribution $μ$ on $\binom{[n]}{k}$ is reduced to sampling from related distributions on $\binom{[t]}{k}$ for $t\ll n$. We show that for strongly Rayleigh distributions, we can can achieve the optimal $t=\widetilde{O}(k)$. Our reduction involves sampling from $\widetilde{O}(1)$ domain-sparsified distributions, all of which can be produced efficiently assuming convenient access to approximate overestimates for marginals of $μ$. Having access to marginals is analogous to having access to the mean and covariance of a continuous distribution, or knowing "isotropy" for the distribution, the key assumption behind the Kannan-Lovász-Simonovits (KLS) conjecture and optimal samplers based on it. We view our result as a moral analog of the KLS conjecture and its consequences for sampling, for discrete strongly Rayleigh measures.

Yang P. Liu, Hoai-An Nguyen, Noah G. Singer et al.

We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dense graphs, we show that $O(n/\varepsilon^2)$ space is sufficient and that $Ω(n)$ space is necessary. In contrast, for graphs with $Θ(n/\varepsilon^2)$ edges, the situation is markedly different: we show that the problem requires $Ω(n \log(\varepsilon^2 n)/\varepsilon^2)$ space for any $\varepsilon=ω(1/\sqrt{n})$, which is tight for the full range of $\varepsilon$. We also give an $Ω(n \log n/\varepsilon^2)$-space lower bound against deterministic algorithms for outputting a $(1-\varepsilon)$ approximation to the value of the maximum cut. Using similar techniques we prove an analogous sharp separation in the streaming space complexity of Densest Subgraph and show that for every constant-arity CSP over a constant-size alphabet and the Similarity problem the space complexity in dense streams can be improved by shaving a logarithmic factor.