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 show variants of spectral sparsification routines can preserve the totalspanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, isequivalent to determinant of a graph Laplacian minor, or equivalently, of anySDDM matrix. Our analyses utilizes this combinatorial connection to bridgebetween statistical leverage scores / effective resistances and the analysis ofrandom graphs by [Janson, Combinatorics, Probability and Computing `94]. Thisleads to a routine that in quadratic time, sparsifies a graph down to about$n^{1.5}$ edges in ways that preserve both the determinant and the distributionof spanning trees (provided the sparsified graph is viewed as a random object).Extending this algorithm to work with Schur complements and approximateCholeksy factorizations leads to algorithms for counting and sampling spanningtrees which are nearly optimal for dense graphs.  We give an algorithm that computes a $(1 \pm \delta)$ approximation to thedeterminant of any SDDM matrix with constant probability in about $n^2\delta^{-2}$ time. This is the first routine for graphs that outperformsgeneral-purpose routines for computing determinants of arbitrary matrices. Wealso give an algorithm that generates in about $n^2 \delta^{-2}$ time aspanning tree of a weighted undirected graph from a distribution with totalvariation distance of $\delta$ from the $w$-uniform distribution .

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees