73 citations · 116 across the 12 of their papers we have counts for
9 papers · 1 filter
A Study of Performance of Optimal Transport
Yihe Dong, Yu Gao, Richard Peng +2
We investigate the problem of efficiently computing optimal transport (OT) distances, which is equivalent to the node-capacitated minimum cost maximum flow problem in a bipartite g…
Flowless: Extracting Densest Subgraphs Without Flow Computations
Digvijay Boob, Yu Gao, Richard Peng +4
We propose a simple and computationally efficient method for dense subgraph discovery, which is a classic problem both in theory and in practice. It is well known that dense subgra…
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
David Durfee, Laxman Dhulipala, Janardhan Kulkarni +3
In this paper we study the problem of dynamically maintaining graph properties under batches of edge insertions and deletions in the massively parallel model of computation. In thi…
Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani, Junxing Wang
We give the first fully dynamic algorithm which maintains a -approximate densest subgraph in worst-case time per update. Dense subgraph discove…
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Timothy Chu, Yu Gao, Richard Peng +3
We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collec…
Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Matthew Fahrbach, Gary L. Miller, Richard Peng +3
Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides a…
On Computing Min-Degree Elimination Orderings
Matthew Fahrbach, Gary L. Miller, Richard Peng +3
We study faster algorithms for producing the minimum degree ordering used to speed up Gaussian elimination. This ordering is based on viewing the non-zero elements of a symmetric p…
Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent
David Durfee, Kevin A. Lai, Saurabh Sawlani
We present preconditioned stochastic gradient descent (SGD) algorithms for the minimization problem in the overdetermined case, where there are far…
Density Independent Algorithms for Sparsifying -Step Random Walks
Gorav Jindal, Pavel Kolev, Richard Peng +1
We give faster algorithms for producing sparse approximations of the transition matrices of -step random walks on undirected, weighted graphs. These transition matrices also for…