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

In this paper we introduce a notion of spectral approximation for directedgraphs. While there are many potential ways one might define approximation fordirected graphs, most of them are too strong to allow sparse approximations ingeneral. In contrast, we prove that for our notion of approximation, suchsparsifiers do exist, and we show how to compute them in almost linear time.  Using this notion of approximation, we provide a general framework forsolving asymmetric linear systems that is broadly inspired by the work of[Peng-Spielman, STOC`14]. Applying this framework in conjunction with oursparsification algorithm, we obtain an almost linear time algorithm for solvingdirected Laplacian systems associated with Eulerian Graphs. Using this solverin the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS`16],we obtain almost linear time algorithms for solving a directed Laplacian linearsystem, computing the stationary distribution of a Markov chain, computingexpected commute times in a directed graph, and more.  For each of these problems, our algorithms improves the previous best runningtimes of $O((nm^{3/4} + n^{2/3} m) \log^{O(1)} (n \kappa \epsilon^{-1}))$ to$O((m + n2^{O(\sqrt{\log{n}\log\log{n}})}) \log^{O(1)} (n \kappa\epsilon^{-1}))$ where $n$ is the number of vertices in the graph, $m$ is thenumber of edges, $\kappa$ is a natural condition number associated with theproblem, and $\epsilon$ is the desired accuracy. We hope these results open thedoor for further studies into directed spectral graph theory, and will serve asa stepping stone for designing a new generation of fast algorithms for directedgraphs.

Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs