
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than GoldbergRao
We give an algorithm for computing exact maximum flows on graphs with m ...
read it

Minor Sparsifiers and the Distributed Laplacian Paradigm
We study distributed algorithms built around edge contraction based vert...
read it

Bipartite Matching in Nearlylinear Time on Moderately Dense Graphs
We present an Õ(m+n^1.5)time randomized algorithm for maximum cardinali...
read it

Concentration Bounds for Cooccurrence Matrices of Markov Chains
Cooccurrence statistics for sequential data are common and important da...
read it

Solving Sparse Linear Systems Faster than Matrix Multiplication
Can linear systems be solved faster than matrix multiplication? While th...
read it

Vertex Sparsification for Edge Connectivity
Graph compression or sparsification is a basic informationtheoretic and...
read it

Faster Graph Embeddings via Coarsening
Graph embeddings are a ubiquitous tool for machine learning tasks, such ...
read it

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
We present a general framework of designing efficient dynamic approximat...
read it

A Study of Performance of Optimal Transport
We investigate the problem of efficiently computing optimal transport (O...
read it

Vertex Sparsifiers for cEdge Connectivity
We show the existence of O(f(c)k) sized vertex sparsifiers that preserve...
read it

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
We consider the classical Minimum Balanced Cut problem: given a graph G,...
read it

Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and kVertex
We study deterministic algorithms for computing graph cuts, with focus o...
read it

Flowless: Extracting Densest Subgraphs Without Flow Computations
We propose a simple and computationally efficient method for dense subgr...
read it

Parallel BatchDynamic Graphs: Algorithms and Lower Bounds
In this paper we study the problem of dynamically maintaining graph prop...
read it

Dynamic Optimality Refuted  For Tournament Heaps
We prove a separation between offline and online algorithms for fingerb...
read it

Fast, Provably convergent IRLS Algorithm for pnorm Linear Regression
Linear regression in ℓ_pnorm is a canonical optimization problem that a...
read it

Flows in Almost Linear Time via Adaptive Preconditioning
We present algorithms for solving a large class of flow and regression p...
read it

Fully Dynamic Spectral Vertex Sparsifiers and Applications
We study dynamic algorithms for maintaining spectral vertex sparsifiers ...
read it

HigherOrder Accelerated Methods for Faster NonSmooth Optimization
We provide improved convergence rates for various nonsmooth optimizatio...
read it

Iterative Refinement for ℓ_pnorm Regression
We give improved algorithms for the ℓ_pregression problem, _xx_p such t...
read it

Solving Directed Laplacian Systems in NearlyLinear Time through Sparse LU Factorizations
We show how to solve directed Laplacian systems in nearlylinear time. G...
read it

Constant Arboricity Spectral Sparsifiers
We show that every graph is spectrally similar to the union of a constan...
read it

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
We develop a framework for graph sparsification and sketching, based on ...
read it

Incomplete Nested Dissection
We present an asymptotically faster algorithm for solving linear systems...
read it

Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Motivated by the study of matrix elimination orderings in combinatorial ...
read it

Fully Dynamic Effective Resistances
In this paper we consider the fullydynamic AllPairs Effective Resistan...
read it

Current Flow Group Closeness Centrality for Complex Networks
Current flow closeness centrality (CFCC) has a better discriminating abi...
read it

On Computing MinDegree Elimination Orderings
We study faster algorithms for producing the minimum degree ordering use...
read it

Spectral Sparsification of RandomWalk Matrix Polynomials
We consider a fundamental algorithmic question in spectral graph theory:...
read it

Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models
Motivated by a sampling problem basic to computational statistical infer...
read it

Runtime Guarantees for Regression Problems
We study theoretical runtime guarantees for a class of optimization prob...
read it
Richard Peng
is this you? claim profile