English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We design fast algorithms for repeatedly sampling from strongly Rayleighdistributions, which include random spanning tree distributions anddeterminantal point processes. For a graph $G=(V, E)$, we show how toapproximately 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 pointprocess on subsets of size $k$ of a ground set of $n$ elements, we show how toapproximately sample in $\widetilde{O}(k^\omega)$ time after an initial$\widetilde{O}(nk^{\omega-1})$ time preprocessing, where $\omega<2.372864$ isthe matrix multiplication exponent. We even improve the state of the art forobtaining a single sample from determinantal point processes, from the priorruntime of $\widetilde{O}(\min\{nk^2, n^\omega\})$ to$\widetilde{O}(nk^{\omega-1})$.  In our main technical result, we achieve the optimal limit on domainsparsification for strongly Rayleigh distributions. In domain sparsification,sampling from a distribution $\mu$ on $\binom{[n]}{k}$ is reduced to samplingfrom related distributions on $\binom{[t]}{k}$ for $t\ll n$. We show that forstrongly 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 efficientlyassuming convenient access to approximate overestimates for marginals of $\mu$.Having access to marginals is analogous to having access to the mean andcovariance of a continuous distribution, or knowing "isotropy" for thedistribution, the key assumption behind the Kannan-Lov\'asz-Simonovits (KLS)conjecture and optimal samplers based on it. We view our result as a moralanalog of the KLS conjecture and its consequences for sampling, for discretestrongly Rayleigh measures.

Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence