Lune

FOCS2022Top-tier venue

Derandomizing Directed Random Walks in Almost-Linear Time

Rasmus Kyng, Simon Meierhans, Maximilian Probst

Abstract

In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear in the number of non-zero entries of L. Previous reductions imply the first deterministic almost-linear time algorithms for computing various fundamental quantities on directed graphs including stationary distributions, personalized PageRank, hitting times and escape probabilities.

We obtain these results by introducing partial symmetrization, a new technique that makes the Laplacian of an Eulerian directed graph "less directed" in a useful sense, which may be of independent interest. The usefulness of this technique comes from two key observations: Firstly, the partially symmetrized Laplacian preconditions the original Eulerian Laplacian well in Richardson iteration, enabling us to construct a solver for the original matrix from a solver for the partially symmetrized one. Secondly, the undirected structure in the partially symmetrized Laplacian makes it possible to sparsify the matrix very crudely, i.e. with large spectral error, and still show that Richardson iterations convergence when using the sparsified matrix as a preconditioner. This allows us to develop deterministic sparsification tools for the partially symmetrized Laplacian.

Together with previous reductions from directed Laplacians to Eulerian Laplacians, our technique results in the first deterministic almost-linear time algorithm for solving linear equations in directed Laplacians. To emphasize the generality of our new technique, we show that two prominent existing (randomized) frameworks for solving linear equations in Eulerian Laplacians can be derandomized in this way: the squaring-based framework of [CKP + 17] and the sparsified Cholesky-based framework of [PS22].

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow cites A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
  • Singular Value Approximation and Sparsifying Random Walks on Directed Graphs cites High-precision Estimation of Random Walks in Small Space
  • Sparsified block elimination for directed laplacians cites High-precision Estimation of Random Walks in Small Space
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. A Deterministic Almost-Linear Time Algorithm for Minimum-Cost FlowJan van den Brand, Li Chen, Richard Peng, Rasmus Kyng et al.FOCS 2023 · 28 citations
  2. Singular Value Approximation and Sparsifying Random Walks on Directed GraphsAmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford et al.FOCS 2023 · 7 citations
  3. Fast Computation of Kemeny's Constant for Directed GraphsHaisong Xia, Zhongzhi ZhangKDD 2024 · 1 citation

Builds on4

  1. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and BeyondJulia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai et al.FOCS 2020 · 76 citations
  2. High-precision Estimation of Random Walks in Small SpaceAmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles et al.FOCS 2020 · 20 citations
  3. Ultrasparse Ultrasparsifiers and Faster Laplacian System SolversArun Jambulapati, Aaron SidfordSODA 2021 · 12 citations
  4. Sparsified block elimination for directed laplaciansRichard Peng, Zhuoqing SongSTOC 2022 · 2 citations

Related papers

  1. Eulerian Graph Sparsification by Effective Resistance DecompositionArun Jambulapati, Sushant Sachdeva, Aaron Sidford, Kevin Tian et al.SODA 2025 · 2 citations
  2. Minor Sparsifiers and the Distributed Laplacian ParadigmSebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng et al.FOCS 2021 · 12 citations
  3. Entrywise Approximate Solutions for SDDM Systems in Almost-Linear TimeAngelo Farfan, Mehrdad Ghadiri, Junzhao YangSTOC 2026
  4. Entrywise Approximation for Matrix Inversion and Linear SystemsMehrdad Ghadiri, Hoai-An Nguyen, Junzhao YangSODA 2026 · 1 citation
  5. Accelerated Evolving Set Processes for Local PageRank ComputationBinbin Huang, Luo Luo, Yanghua Xiao, Deqing Yang et al.NeurIPS 2025 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines