7 citations · 10 across the 7 of their papers we have counts for
9 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…
Near-Optimal Oracle Bounds for Isotropic Rounding
Yang P. Liu, Richard Peng, Alicia Stepin +1
We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body in can be rou…
Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
Noah Amsel, Yves Baumann, Paul Beckman +33
This document presents a series of open questions arising in matrix computations, i.e., the numerical solution of linear algebra problems. It is a result of working groups at the w…
Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
Yang P. Liu, Richard Peng, Colin Tang +2
Consider the empirical risk minimization (ERM) problem, which is stated as follows. Let be compact convex sets with for $i \in [m…
Approximate Spanning Tree Counting from Uncorrelated Edge Sets
Yang P. Liu, Richard Peng, Junzhao Yang
We show an time algorithm that on a graph with edges and vertices outputs its spanning tree count up to a multiplicative factor with…
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
Jan van den Brand, Li Chen, Rasmus Kyng +5
We provide an algorithm which, with high probability, maintains a -approximate maximum flow on an undirected graph undergoing -edge additions in amortized $m^{o(1)} ε^{-3…
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
Jan van den Brand, Li Chen, Rasmus Kyng +5
We give a deterministic time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral dem…
-norm Flow Diffusion in Near-Linear Time
Li Chen, Richard Peng, Di Wang
Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervi…
Improved Parallel Algorithms for Spanners and Hopsets
Gary L. Miller, Richard Peng, Adrian Vladu +1
We use exponential start time clustering to design faster and more work-efficient parallel graph algorithms involving distances. Previous algorithms usually rely on graph decomposi…