6 citations · 6 across the 4 of their papers we have counts for
7 papers
Fully Dynamic Random-Walk Quantities on Undirected Expanders and -Uniform Directed Graphs
Richard Peng, Sushant Sachdeva, Junzhao Yang +1
We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has sp…
Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg +2
We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data struc…
An Online Sparsification Algorithm from the Book
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg +2
In their seminal paper [Cohen et al., 2016], Cohen, Musco, and Pachocki proposed a natural and simple online spectral sparsification algorithm: rows $a_1, a_2, \ldots \in \mathbb{R…
Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
Yibin Zhao
Recent years have seen extensive research on directed graph sparsification. In this work, we initiate the study of fast fully dynamic spectral and cut sparsification algorithms for…
Eulerian Graph Sparsification by Effective Resistance Decomposition
Arun Jambulapati, Sushant Sachdeva, Aaron Sidford +2
We provide an algorithm that, given an -vertex -edge Eulerian graph with polynomially bounded weights, computes an -edge $\vare…
Better Sparsifiers for Directed Eulerian Graphs
Sushant Sachdeva, Anvith Thudi, Yibin Zhao
Spectral sparsification for directed Eulerian graphs is a key component in the design of fast algorithms for solving directed Laplacian linear systems. Directed Laplacian linear sy…
A Simple and Efficient Parallel Laplacian Solver
Sushant Sachdeva, Yibin Zhao
A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linea…