24 citations · 151 across the 43 of their papers we have counts for
34 papers · 1 filter
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…
A Tight Bound on Localization of Electrical Flows
Ori Gurel-Gurevich, Asaf Nachmias, Sushant Sachdeva
We prove that for any unweighted graph on n vertices the L1 norm of a unit electric current between the endpoints of a random edge is at most 2 log n. Furthermore, we show that on…
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…
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Jan van den Brand, Li Chen, Rasmus Kyng +4
We give the first almost-linear total time algorithm for deciding if a flow of cost at most still exists in a directed graph, with edge costs and capacities, undergoing decreme…
Optimal Electrical Oblivious Routing on Expanders
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg +1
In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an -edge graph that is a -expander, i.e.…
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…