93 citations · 537 across the 73 of their papers we have counts for
5 papers · 2 filters
Sparsified Block Elimination for Directed Laplacians
Richard Peng, Zhuoqing Song
We show that the sparsified block elimination algorithm for solving undirected Laplacian linear systems from [Kyng-Lee-Peng-Sachdeva-Spielman STOC'16] directly works for directed L…
Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows
Monika Henzinger, Billy Jin, Richard Peng +1
We study the problem of finding flows in undirected graphs so as to minimize the weighted -norm of the flow for any . When , the problem is that of finding an electr…
Hardness of Graph-Structured Algebraic and Symbolic Problems
Jingbang Chen, Yu Gao, Yufan Huang +2
In this paper, we study the hardness of solving graph-structured linear systems with coefficients over a finite field and over a polynomial ring $\mathbb{F}[x_1,\ldo…
Faster -Norm Regression Using Sparsity
Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala
For a matrix with , we consider the dual problems of and $\min_{A^\top x=b} \|x\|_p^p,\, b\in \math…
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
Yu Gao, Yang P. Liu, Richard Peng
We give an algorithm for computing exact maximum flows on graphs with edges and integer capacities in the range in $\widetilde{O}(m^{\frac{3}{2} - \frac{1}{328}} \log…