We present an algorithm that on input of an $n$-vertex $m$-edge weighted graph $G$ and
a value $k$ produces an incremental sparsifier $\hat{G}$ with $n-1 + m/k$ edges, such that …

We show an algorithm for solving symmetric diagonally dominant (SDD) linear systems with
m non-zero entries to a relative error of ε in O(m log 1/2 n log c n log(1/ε)) time. Our …

We present an $\tilde{O}(m+n^{1.5})$ -time randomized algorithm for maximum cardinality
bipartite matching and related problems (eg transshipment, negative-weight shortest paths, …

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed
graphs with m edges and polynomially bounded integral demands, costs, and capacities …

The number of triangles is a computationally expensive graph statistic frequently used in
complex network analysis (eg, transitivity ratio), in various random graph models (eg, …

We present the first parallel algorithm for solving systems of linear equations in symmetric,
diagonally dominant (SDD) matrices that runs in polylogarithmic time and nearly-linear work. …

We present an improved algorithm for solving symmetrically diagonally dominant linear systems.
On input of an n×n symmetric diagonally dominant matrix A with m non-zero entries and …

Random sampling has become a critical tool in solving massive matrix problems. For linear
regression, a small, manageable set of data rows can be randomly selected to approximate …

We show an improved parallel algorithm for decomposing an undirected unweighted graph
into small diameter pieces with a small fraction of the edges in between. These …

We give a simple algorithm to efficiently sample the rows of a matrix while preserving the p-norms
of its product with vectors. Given an n * d matrix A, we find with high probability and in …