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/

Zendy Plus

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

Zendy Tools

Zendy Open

We develop a framework for graph sparsification and sketching, based on a newtool, short cycle decomposition -- a decomposition of an unweighted graph intoan edge-disjoint collection of short cycles, plus few extra edges. A simpleobservation gives that every graph G on n vertices with m edges can bedecomposed in $O(mn)$ time into cycles of length at most $2\log n$, and at most$2n$ extra edges. We give an $m^{1+o(1)}$ time algorithm for constructing ashort cycle decomposition, with cycles of length $n^{o(1)}$, and $n^{1+o(1)}$extra edges. These decompositions enable us to make progress on several openquestions:  * We give an algorithm to find $(1\pm\epsilon)$-approximations to effectiveresistances of all edges in time $m^{1+o(1)}\epsilon^{-1.5}$, improving overthe previous best of $\tilde{O}(\min\{m\epsilon^{-2},n^2 \epsilon^{-1}\})$.This gives an algorithm to approximate the determinant of a Laplacian up to$(1\pm\epsilon)$ in $m^{1 + o(1)} + n^{15/8+o(1)}\epsilon^{-7/4}$ time.  * We show existence and efficient algorithms for constructing graphicalspectral sketches -- a distribution over sparse graphs H such that for a fixedvector $x$, we have w.h.p. $x'L_Hx=(1\pm\epsilon)x'L_Gx$ and$x'L_H^+x=(1\pm\epsilon)x'L_G^+x$. This implies the existence ofresistance-sparsifiers with about $n\epsilon^{-1}$ edges that preserve theeffective resistances between every pair of vertices up to $(1\pm\epsilon).$  * By combining short cycle decompositions with known tools in graphsparsification, we show the existence of nearly-linear sized degree-preservingspectral sparsifiers, as well as significantly sparser approximations ofdirected graphs. The latter is critical to recent breakthroughs on fasteralgorithms for solving linear systems in directed Laplacians.  Improved algorithms for constructing short cycle decompositions will lead toimprovements for each of the above results.

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions