Richard Peng

SODA Conference 2024 Conference Paper

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

• Jan van den Brand
• Li Chen 0028
• Rasmus Kyng
• Yang P. Liu
• Richard Peng
• Maximilian Probst Gutenberg
• Sushant Sachdeva
• Aaron Sidford

We provide an algorithm which, with high probability, maintains a (1 — ɛ)-approximate maximum flow on an undirected graph undergoing m -edge additions in amortized m o (1) ɛ -3 time per update. To obtain this result, we provide a more general algorithm that solves what we call the incremental, thresholded, p-norm flow problem that asks to determine the first edge-insertion in an undirected graph that causes the minimum ℓ p -norm flow to decrease below a given threshold in value. Since we solve this thresholded problem, our data structure succeeds against an adaptive adversary that can only see the data structure's output. Furthermore, since our algorithm holds for p = 2, we obtain improved algorithms for dynamically maintaining the effective resistance between a pair of vertices in an undirected graph undergoing edge insertions. Our algorithm builds upon previous dynamic algorithms for approximately solving the minimum-ratio cycle problem that underlie previous advances on the maximum flow problem [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS ‘22] as well as recent dynamic maximum flow algorithms [v. d. Brand-Liu-Sidford, STOC ‘23]. Instead of using interior point methods, which were a key component of these recent advances, our algorithm uses an optimization method based on ℓ p -norm iterative refinement and the multiplicative weight update method. This ensures a monotonicity property in the minimum-ratio cycle subproblems that allows us to apply known data structures and bypass issues arising from adaptive queries. * The full version of the paper can be accessed at https: //arxiv. org/abs/2311. 03174

FOCS Conference 2023 Conference Paper

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow

• Jan van den Brand
• Li Chen 0028
• Richard Peng
• Rasmus Kyng
• Yang P. Liu
• Maximilian Probst Gutenberg
• Sushant Sachdeva
• Aaron Sidford

We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities. As a consequence, we obtain the first running time improvement for deterministic algorithms that compute maximum-flow in graphs with polynomial bounded capacities since the work of Goldberg-Rao [J. ACM ’98]. Our algorithm builds on the framework of Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS ’22] that computes an optimal flow by computing a sequence of $m^{1+o(1)}$-approximate undirected minimum-ratio cycles. We develop a deterministic dynamic graph data-structure to compute such a sequence of minimum-ratio cycles in an amortized $m^{o(1)}$ time per edge update. Our key technical contributions are deterministic analogues of the vertex sparsification and edge sparsification components of the data-structure from Chen et al. For the vertex sparsification component, we give a method to avoid the randomness in Chen et al. which involved sampling random trees to recurse on. For the edge sparsification component, we design a deterministic algorithm that maintains an embedding of a dynamic graph into a sparse spanner. We also show how our dynamic spanner can be applied to give a deterministic data structure that maintains a fully dynamic low-stretch spanning tree on graphs with polynomially bounded edge lengths, with subpolynomial average stretch and subpolynomial amortized time per edge update.

FOCS Conference 2023 Conference Paper

The Bit Complexity of Efficient Continuous Optimization

• Mehrdad Ghadiri
• Richard Peng
• Santosh S. Vempala

We analyze the bit complexity of efficient algorithms for fundamental optimization problems, such as linear regression, p-norm regression, and linear programming (LP). State-of-the-art algorithms are iterative, and in terms of the number of arithmetic operations, they match the current time complexity of multiplying two n-by-n matrices (up to polylogarithmic factors). However, previous work has typically assumed infinite precision arithmetic, and due to complicated inverse maintenance techniques, the actual running times of these algorithms are unknown. To settle the running time and bit complexity of these algorithms, we demonstrate that a core common subroutine, known as inverse maintenance, is backward-stable. Additionally, we show that iterative approaches for solving constrained weighted regression problems can be accomplished with bounded-error preconditioners. Specifically, we prove that linear programs can be solved approximately in matrix multiplication time multiplied by polylog factors that depend on the condition number $\kappa$ of the matrix and the inner and outer radius of the LP problem. p-norm regression can be solved approximately in matrix multiplication time multiplied by polylog factors in $\kappa$. Lastly, linear regression can be solved approximately in input-sparsity time multiplied by polylog factors in $\kappa$. Furthermore, we present results for achieving lower than matrix multiplication time for p-norm regression by utilizing faster solvers for sparse linear systems.

STOC Conference 2022 Conference Paper

Faster maxflow via improved dynamic spectral vertex sparsifiers

• Jan van den Brand
• Yu Gao 0001
• Arun Jambulapati
• Yin Tat Lee
• Yang P. Liu
• Richard Peng
• Aaron Sidford

We make several advances broadly related to the maintenance of electrical flows in weighted graphs undergoing dynamic resistance updates, including: (1) More efficient dynamic spectral vertex sparsification, achieved by faster length estimation of random walks in weighted graphs using Morris counters [Morris 1978, Nelson-Yu 2020]. (2) A direct reduction from detecting edges with large energy in dynamic electric flows to dynamic spectral vertex sparsifiers. (3) A procedure for turning algorithms for estimating a sequence of vectors under updates from an oblivious adversary to one that tolerates adaptive adversaries via the Gaussian-mechanism from differential privacy. Combining these pieces with modifications to prior robust interior point frameworks gives an algorithm that on graphs with m edges computes a mincost flow with edge costs and capacities in [1, U ] in time O ( m 3/2−1/58 log 2 U ). In prior and independent work, [Axiotis-Mądry-Vladu FOCS 2021] also obtained an improved algorithm for sparse mincost flows on capacitated graphs. Our algorithm implies a O ( m 3/2−1/58 log U ) time maxflow algorithm, improving over the O ( m 3/2−1/328 log U ) time maxflow algorithm of [Gao-Liu-Peng FOCS 2021].

FOCS Conference 2022 Conference Paper

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

• Li Chen 0028
• Rasmus Kyng
• Yang P. Liu
• Richard Peng
• Maximilian Probst Gutenberg
• Sushant Sachdeva

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 in $m^{1+o(1)}$ time. Our algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using a new dynamic graph data structure. Our framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.

SODA Conference 2022 Conference Paper

Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time

• Sally Dong
• Yu Gao 0001
• Gramoz Goranci
• Yin Tat Lee
• Richard Peng
• Sushant Sachdeva
• Guanghao Ye

We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm for this problem was based on interior point methods (IPMs) and worked for general sparse graphs in O ( n 1. 5 poly(log n )) time [Daitch-Spielman, STOC'08]. Intuitively, Ω( n 1. 5 ) is a natural runtime barrier for IPM based methods, since they require iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested-dissection [Lipton-Rose-Tarjan, JSTOR'79] and approximate Schur complements [Kyng-Sachdeva, FOCS'16]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly update time, resulting in a total running time of O(n · poly(log n )). Our results immediately extend to all families of separable graphs.

STOC Conference 2022 Conference Paper

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 Laplacians. Given access to a sparsification algorithm that, on graphs with n vertices and m edges, takes time T S ( m ) to output a sparsifier with N S ( n ) edges, our algorithm solves a directed Eulerian system on n vertices and m edges to є relative accuracy in time O ( T S ( m ) + N S ( n )log n log( n /є)) + Õ( T S ( N S ( n )) log n ), where the Õ(·) notation hides loglog( n ) factors. By previous results, this implies improved runtimes for linear systems in strongly connected directed graphs, PageRank matrices, and asymmetric M-matrices. When combined with slower constructions of smaller Eulerian sparsifiers based on short cycle decompositions, it also gives a solver algorithm that, after pre-processing the matrix in O ( n 2 log O (1) n ) time, takes O ( n log 5 n log( n / є)) time per solve. At the core of our analyses are constructions of augmented matrices whose Schur complements encode error matrices.

FOCS Conference 2021 Conference Paper

2-norm Flow Diffusion in Near-Linear Time

• Li Chen 0028
• Richard Peng
• Di Wang 0005

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-supervised learning on graphs. In this paper, we study computationally efficient diffusion primitives beyond random walk. We design an near-linear time randomized algorithm for the 2-norm flow diffusion problem, a recently proposed diffusion model based on network flow with demonstrated graph clustering related applications both in theory and in practice. Examples include finding locally-biased low conductance cuts. Using a known connection between the optimal dual solution of the flow diffusion problem and the local cut structure, our algorithm gives an alternative approach for finding such cuts in nearly linear time. From a technical point of view, our algorithm contributes a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of nearly linear time Laplacian system solvers, but requires several new tools: vertex elimination under constraints, a new family of graph ultra-sparsifiers, and ac-celerated proximal gradient methods with inexact proximal mapping computation. See https: //arxiv. org/abs/2105. 14629 for the full version of this paper.

FOCS Conference 2021 Conference Paper

Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

• Yu Gao 0001
• Yang P. Liu
• Richard Peng

We give an algorithm for computing exact maximum flows on graphs with $m$ edges and integer capacities in the range [ $1, U$ ] in $\tilde{O}(m^{\frac{3}{2}-\frac{1}{328}}\log U)$ time. 1 1 We use $\tilde{O}(\cdot)$ to suppress logarithmic factors in $m$. For sparse graphs with polynomially bounded integer capacities, this is the first improvement over the $\tilde{O}(m^{1. 5}\log U)$ time bound from [Goldberg-Rao JACM '98]. Our algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [Mądry JACM '16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.

FOCS Conference 2021 Conference Paper

Minor Sparsifiers and the Distributed Laplacian Paradigm

• Sebastian Forster
• Gramoz Goranci
• Yang P. Liu
• Richard Peng
• Xiaorui Sun
• Mingquan Ye

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of $O(n^{o(1)}(\sqrt{n}+D))$, and thus almost matches the lower bound of $\widetilde{\Omega}(\sqrt{n}+D)$, where $n$ is the number of nodes in the network and $D$ is its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications. At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that the algorithm still produces a high-quality subspace spectral sparsifier by carefully setting up and analyzing matrix martingales. Combining this vertex reduction recursively with both tree and elimination-based preconditioners leads to our algorithm for solving Laplacian systems. The construction of the elimination-based preconditioners is based on computing short random walks, and we introduce a new technique for reducing the congestion incurred by the simulation of these walks on weighted graphs.

SODA Conference 2021 Conference Paper

Solving Sparse Linear Systems Faster than Matrix Multiplication

• Richard Peng
• Santosh S. Vempala

Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph structured linear systems, in the general setting, the bit complexity of solving an n × n linear system Ax = b is Õ ( n ω ), where ω < 2. 372864 is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with poly( n ) condition number. In this paper, we present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any ω > 2. This speedup holds for any input matrix A with o ( n ω –1 /log( κ ( A ))) non-zeros, where κ ( A ) is the condition number of A. For poly( n )-conditioned matrices with Õ ( n ) nonzeros, and the current value of ω, the bit complexity of our algorithm to solve to within any 1/poly( n ) error is O ( n 2. 331645 ). Our algorithm can be viewed as an efficient, randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly et al. ISSAC ‘06 ‘07] for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices.

SODA Conference 2021 Conference Paper

Vertex Sparsification for Edge Connectivity

• Parinya Chalermsook
• Syamantak Das
• Yunbum Kook
• Bundit Laekhanukit
• Yang P. Liu
• Richard Peng
• Mark Sellke
• Daniel Vaz 0001

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether (1 + ∊ )-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter c, find a smaller graph, which we call connectivity-c mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivity- c mimicking networks with O ( kc 4 ) edges exist and can be found in time m ( c log n ) O ( c ). We also give a separate algorithm that constructs such graphs with k · O ( c ) 2 c edges in time mc O ( c ) log O (1) n. These results lead to the first data structures for answering fully dynamic offline c -edge-connectivity queries for c ≥ 4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.

FOCS Conference 2020 Conference Paper

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

• Julia Chuzhoy
• Yu Gao 0001
• Jason Li 0006
• Danupon Nanongkai
• Richard Peng
• Thatchaphol Saranurak

We consider the classical Minimum Balanced Cut problem: given a graph G, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first deterministic, almost-linear time approximation algorithm for this problem. Specifically, our algorithm, given an n-vertex m-edge graph G and any parameter 1 ≤ r ≤ O(logn), computes a (logm) r2 -approximation for Minimum Balanced Cut in G, in time O(m 1+O(1/r)+o(1) ·(logm) O(r2 )). In particular, we obtain a (logm) 1/ε -approximation in time m 1+O(√{ε}) for any constant, and a (logm) f(m) -approximation in time m 1+o(1), for any slowly growing function f(m). We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of G that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an n-vertex graph is n o(1), thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in n factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.

NeurIPS Conference 2020 Conference Paper

A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices

• Jiezhong Qiu
• Chi Wang
• Ben Liao
• Richard Peng
• Jie Tang

We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a regular (aperiodic and irreducible) finite Markov chain. Specially, consider a random walk on a regular Markov chain and a Hermitian matrix-valued function on its state space. Our result gives exponentially decreasing bounds on the tail distributions of the extreme eigenvalues of the sample mean matrix. Our proof is based on the matrix expander (regular undirected graph) Chernoff bound [Garg et al. STOC '18] and scalar Chernoff-Hoeffding bounds for Markov chains [Chung et al. STACS '12]. Our matrix Chernoff bound for Markov chains can be applied to analyze the behavior of co-occurrence statistics for sequential data, which have been common and important data signals in machine learning. We show that given a regular Markov chain with n states and mixing time t, we need a trajectory of length O(t(log(n) + log(t))/e^2) to achieve an estimator of the co-occurrence matrix with error bound e. We conduct several experiments and the experimental results are consistent with the exponentially fast convergence rate from theoretical analysis. Our result gives the first bound on the convergence rate of the co-occurrence matrix and the first sample complexity analysis in graph representation learning.

FOCS Conference 2020 Conference Paper

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

• Jan van den Brand
• Yin Tat Lee
• Danupon Nanongkai
• Richard Peng
• Thatchaphol Saranurak
• Aaron Sidford
• Zhao Song 0002
• Di Wang 0005

We present an $\tilde{O}(m+n^{1. 5})$ -time randomized algorithm for maximum cardinality bipartite matching and related problems (e. g. transshipment, negative-weight shortest paths, and optimal transport) on m-edge, n-node graphs. For maximum cardinality bipartite matching on moderately dense graphs, i. e. $m=\Omega(n^{1. 5})$, our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic $O(m\sqrt{n})$ -time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and $\widetilde{O}(n^{\omega})$ -time algorithms [Ibarra-Moran 1981] (where currently $\omega\approx 2. 373$ ). On sparser graphs, i. e. when $m=n^{9/8+\delta}$ for any constant $\delta > 0$, our result improves upon the recent advances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an $\widetilde{O}(m^{4/3+o(1)})$ runtime. We obtain these results by combining and advancing recent lines of research in interior point methods (IPMs) and dynamic graph algorithms. First, we simplify and improve the IPM of [v. d. Brand-Lee-Sidford-Song 2020], providing a general primal-dual IPM framework and new sampling-based techniques for handling infeasibility induced by approximate linear system solvers. Second, we provide a simple sublinear-time algorithm for detecting and sampling high-energy edges in electric flows on expanders and show that when combined with recent advances in dynamic expander decompositions, this yields efficient data structures for maintaining the iterates of both [v. d. Brand et al. ] and our new IPMs. Combining this general machinery yields a simpler $\widetilde{O}(n\sqrt{m})$ time algorithm for matching based on the logarithmic barrier function, and our state-of-the-art $\widetilde{O}(m+n^{1. 5})$ time algorithm for matching based on the [Lee-Sidford 2014] barrier (as regularized in [v. d. Brand et al. ]).

FOCS Conference 2020 Conference Paper

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

• Li Chen 0028
• Gramoz Goranci
• Monika Henzinger
• Richard Peng
• Thatchaphol Saranurak

We present a general framework of designing efficient dynamic approximate algorithms for optimization problems on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1)A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in $\tilde{O}(n^{2/3})$ 1 1 The $\tilde{O}(\cdot)$ notation is used in this paper to hide poly-logarithmic factors. amortized time against an oblivious adversary, and $\tilde{O}(m^{3/4})$ time against an adaptive adversary. (2)An incremental data structure that maintains $O(1)$ - approximate shortest path in $n^{o(1)}$ time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in $\tilde{O}(n^{2/3 +o(1)})$ amortized time per operation. (3)A fully-dynamic algorithm that approximates all-pair effective resistance up to an ( $1+\epsilon$ ) factor in $\tilde{O}(n^{2/3+o(1)}\epsilon^{-O(1)})$ amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as $j$ -trees) and approximately captures the cut-flow and metric structure of the graph. The $O(1)$ -approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. See https: //arxiv. org/pdf/2005. 02368. pdf for the full version of this paper.

ICML Conference 2020 Conference Paper

Faster Graph Embeddings via Coarsening

• Matthew Fahrbach
• Gramoz Goranci
• Richard Peng
• Sushant Sachdeva
• Chi Wang 0001

Graph embeddings are a ubiquitous tool for machine learning tasks, such as node classification and link prediction, on graph-structured data. However, computing the embeddings for large-scale graphs is prohibitively inefficient even if we are interested only in a small subset of relevant vertices. To address this, we present an efficient graph coarsening approach, based on Schur complements, for computing the embedding of the relevant vertices. We prove that these embeddings are preserved exactly by the Schur complement graph that is obtained via Gaussian elimination on the non-relevant vertices. As computing Schur complements is expensive, we give a nearly-linear time algorithm that generates a coarsened graph on the relevant vertices that provably matches the Schur complement in expectation in each iteration. Our experiments involving prediction tasks on graphs demonstrate that computing embeddings on the coarsened graph, rather than the entire graph, leads to significant time savings without sacrificing accuracy.

SODA Conference 2020 Conference Paper

Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds

• Laxman Dhulipala
• David Durfee
• Janardhan Kulkarni
• Richard Peng
• Saurabh Sawlani
• Xiaorui Sun

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 this setting, the graph is stored on a number of machines, each having space strongly sublinear with respect to the number of vertices, that is, n ϵ for some constant 0 < ϵ < 1. Our goal is to handle batches of updates and queries where the data for each batch fits onto one machine in constant rounds of parallel computation, as well as to reduce the total communication between the machines. This objective corresponds to the gradual buildup of databases over time, while the goal of obtaining constant rounds of communication for problems in the static setting has been elusive for problems as simple as undirected graph connectivity. We give an algorithm for dynamic graph connectivity in this setting with constant communication rounds and communication cost almost linear in terms of the batch size. Our techniques combine a new graph contraction technique, an independent random sample extractor from correlated samples, as well as distributed data structures supporting parallel updates and queries in batches. We also illustrate the power of dynamic algorithms in the MPC model by showing that the batched version of the adaptive connectivity problem is P-complete in the centralized setting, but sub-linear sized batches can be handled in a constant number of rounds. Due to the wide applicability of our approaches, we believe it represents a practically-motivated workaround to the current difficulties in designing more efficient massively parallel static graph algorithms.

NeurIPS Conference 2019 Conference Paper

Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression

• Deeksha Adil
• Richard Peng
• Sushant Sachdeva

Linear regression in L p-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Generic convex optimization algorithms for solving L p-regression are slow in practice. Iteratively Reweighted Least Squares (IRLS) is an easy to implement family of algorithms for solving these problems that has been studied for over 50 years. However, these algorithms often diverge for p > 3, and since the work of Osborne (1985), it has been an open problem whether there is an IRLS algorithm that converges for p > 3. We propose p-IRLS, the first IRLS algorithm that provably converges geometrically for any p \in [2, \infty). Our algorithm is simple to implement and is guaranteed to find a high accuracy solution in a sub-linear number of iterations. Our experiments demonstrate that it performs even better than our theoretical bounds, beats the standard Matlab/CVX implementation for solving these problems by 10–50x, and is the fastest among available implementations in the high-accuracy regime.

STOC Conference 2019 Conference Paper

Flows in almost linear time via adaptive preconditioning

• Rasmus Kyng
• Richard Peng
• Sushant Sachdeva
• Di Wang 0005

We present algorithms for solving a large class of flow and regression problems on unit weighted graphs to (1 + 1 / poly ( n )) accuracy in almost-linear time. These problems include ℓ p -norm minimizing flow for p large ( p ∈ [ω(1), o (log 2/3 n ) ]), and their duals, ℓ p -norm semi-supervised learning for p close to 1. As p tends to infinity, p -norm flow and its dual tend to max-flow and min-cut respectively. Using this connection and our algorithms, we give an alternate approach for approximating undirected max-flow, and the first almost-linear time approximations of discretizations of total variation minimization objectives. Our framework is inspired by the routing-based solver for Laplacian linear systems by Spielman and Teng (STOC ’04, SIMAX ’14), and is based on several new tools we develop, including adaptive non-linear preconditioning, tree-routings, and (ultra-)sparsification for mixed ℓ 2 and ℓ p norm objectives.

STOC Conference 2019 Conference Paper

Fully dynamic spectral vertex sparsifiers and applications

• David Durfee
• Yu Gao 0001
• Gramoz Goranci
• Richard Peng

We study dynamic algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals T of our choice. Such objects preserve pairwise resistances, solutions to systems of linear equations, and energy of electrical flows between the terminals in T . We give a data structure that supports insertions and deletions of edges, and terminal additions, all in sublinear time. We then show the applicability of our result to the following problems. (1) A data structure for dynamically maintaining solutions to Laplacian systems L x = b , where L is the graph Laplacian matrix and b is a demand vector. For a bounded degree, unweighted graph, we support modifications to both L and b while providing access to є-approximations to the energy of routing an electrical flow with demand b , as well as query access to entries of a vector x such that ∥x− L † b ∥ L ≤ є ∥ L † b ∥ L in Õ( n 11/12 є −5 ) expected amortized update and query time. (2) A data structure for maintaining fully dynamic All-Pairs Effective Resistance. For an intermixed sequence of edge insertions, deletions, and resistance queries, our data structures returns (1 ± є)-approximation to all the resistance queries against an oblivious adversary with high probability. Its expected amortized update and query times are Õ(min( m 3/4 , n 5/6 є −2 ) є −4 ) on an unweighted graph, and Õ( n 5/6 є −6 ) on weighted graphs. The key ingredients in these results are (1) the intepretation of Schur complement as a sum of random walks, and (2) a suitable choice of terminals based on the behavior of these random walks to make sure that the majority of walks are local, even when the graph itself is highly connected and (3) maintenance of these local walks and numerical solutions using data structures. These results together represent the first data structures for maintain key primitives from the Laplacian paradigm for graph algorithms in sublinear time without assumptions on the underlying graph topologies. The importance of routines such as effective resistance, electrical flows, and Laplacian solvers in the static setting make us optimistic that some of our components can provide new building blocks for dynamic graph algorithms.

SODA Conference 2019 Conference Paper

Iterative Refinement for ℓp-norm Regression

• Deeksha Adil
• Rasmus Kyng
• Richard Peng
• Sushant Sachdeva

FOCS Conference 2018 Conference Paper

Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm

• Matthew Fahrbach
• Gary L. Miller
• Richard Peng
• Saurabh Sawlani
• Junxing Wang
• Shen Chen Xu

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 access to approximate fill degrees of a matrix undergoing elimination in polylogarithmic time per elimination and query. We then study the problem of using this data structure in the minimum degree algorithm, which is a widely-used heuristic for producing elimination orderings for sparse matrices by repeatedly eliminating the vertex with (approximate) minimum fill degree. This leads to a nearly-linear time algorithm for generating approximate greedy minimum degree orderings. Despite extensive studies of algorithms for elimination orderings in combinatorial scientific computing, our result is the first rigorous incorporation of randomized tools in this setting, as well as the first nearly-linear time algorithm for producing elimination orderings with provable approximation guarantees. While our sketching data structure readily works in the oblivious adversary model, by repeatedly querying and greedily updating itself, it enters the adaptive adversarial model where the underlying sketches become prone to failure due to dependency issues with their internal randomness. We show how to use an additional sampling procedure to circumvent this problem and to create an independent access sequence. Our technique for decorrelating interleaved queries and updates to this randomized data structure may be of independent interest.

FOCS Conference 2018 Conference Paper

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions

• Timothy Chu
• Yu Gao 0001
• Richard Peng
• Sushant Sachdeva
• Saurabh Sawlani
• Junxing Wang

We develop a framework for graph sparsification based on a new tool, short cycle decomposition for graphs - a decomposition of a graph into a collection of short cycles, plus a small number of extra edges. A simple observation gives that every graph G on n vertices with m edges can be decomposed in O(mn) time into cycles of length at most 2 log n, and at most 2n extra edges. We give an m 1+o(1) time algorithm for constructing a short cycle decomposition of the graph, with cycles of length n o(1), and n 1+o(1) extra edges. Both the existential and algorithmic variants of this decomposition enable us to make progress on several open problems in randomized graph algorithms. 1. We present an algorithm that runs in time m 1+o(1) ε -1. 5 and returns (1 ± ε)-approximations to effective resistances of all edges, improving over the previous best of Õ(min{mε -2, n 2 ε -1 }) This gives an algorithm to approximate the determinant of a graph Laplacian up to a factor of (1 ± ε) in roughly m + n 15/8 ε -7/4. 2. We show existence and efficient algorithms for constructing graphical spectral sketches - a distribution over sparse graphs H with about nε -1 edges such that for a fixed vector x, we have x T L H x = (1 ± eps) x T L G x and x T L+ H x = (1 ± ε) x T L+ G x with high probability, where L is the graph Laplacian and L+ is its pseudoinverse. This implies resistance-sparsifiers with about nε edges that preserve the effective resistances between every pair of vertices up to (1 + eps). 3. By combining short cycle decomposition with importance sampling, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of directed graphs. The latter is critical to recent breakthroughs on faster algorithms for directed random walks and linear systems in directed Laplacian. The running time and output qualities of our spectral sketch and degree-preserving (directed) sparsification algorithms are limited by the efficiency of our routines for producing short cycle decompositions. Improved algorithms for short cycle decompositions will lead to improvements for each of these algorithms.

STOC Conference 2018 Conference Paper

Incomplete nested dissection

• Rasmus Kyng
• Richard Peng
• Robert Schwieterman
• Peng Zhang 0052

We present an asymptotically faster algorithm for solving linear systems in well-structured 3-dimensional truss stiffness matrices. These linear systems arise from linear elasticity problems, and can be viewed as extensions of graph Laplacians into higher dimensions. Faster solvers for the 2-D variants of such systems have been studied using generalizations of tools for solving graph Laplacians [Daitch-Spielman CSC’07, Shklarski-Toledo SIMAX’08]. Given a 3-dimensional truss over n vertices which is formed from a union of k convex structures (tetrahedral meshes) with bounded aspect ratios, whose individual tetrahedrons are also in some sense well-conditioned, our algorithm solves a linear system in the associated stiffness matrix up to accuracy є in time O ( k 1/3 n 5/3 log(1 / є)). This asymptotically improves the running time O ( n 2 ) by Nested Dissection for all k ≪ n . We also give a result that improves on Nested Dissection even when we allow any aspect ratio for each of the k convex structures (but we still require well-conditioned individual tetrahedrons). In this regime, we improve on Nested Dissection for k ≪ n 1/44 . The key idea of our algorithm is to combine nested dissection and support theory. Both of these techniques for solving linear systems are well studied, but usually separately. Our algorithm decomposes a 3-dimensional truss into separate and balanced regions with small boundaries. We then bound the spectrum of each such region separately, and utilize such bounds to obtain improved algorithms by preconditioning with partial states of separator-based Gaussian elimination.

FOCS Conference 2018 Conference Paper

Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations

• Michael B. Cohen
• Jonathan A. Kelner
• Rasmus Kyng
• John Peebles
• Richard Peng
• Anup B. Rao
• Aaron Sidford

In this paper, we show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an n × n Eulerian directed Laplacian with m nonzero entries, we show how to compute an ε-approximate solution in time O(m log O(1) (n) log (1/ε)). Through reductions from [Cohen et al. FOCS'16], this gives the first nearly-linear time algorithms for computing ε-approximate solutions to row or column diagonally dominant linear systems (including arbitrary directed Laplacians) and computing ε-approximations to various properties of random walks on directed graphs, including stationary distributions, personalized PageRank vectors, hitting times, and escape probabilities. These bounds improve upon the recent almost-linear algorithms of [Cohen et al. STOC'17], which gave an algorithm to solve Eulerian Laplacian systems in time O((m+n2 O(√ log n log log n) )log O(1) (n ε -1 )). To achieve our results, we provide a structural result that we believe is of independent interest. We show that Eulerian Laplacians (and therefore the Laplacians of all strongly connected directed graphs) have sparse approximate LU-factorizations. That is, for every such directed Laplacian there are lower upper triangular matrices each with at most Õ(n) nonzero entries such that there product spectrally approximates the directed Laplacian in an appropriate norm. This claim can be viewed as an analog of recent work on sparse Cholesky factorizations of Laplacians of undirected graphs. We show how to construct such factorizations in nearly-linear time and prove that once constructed they yield nearly-linear time algorithms for solving directed Laplacian systems.

SODA Conference 2017 Conference Paper

A Framework for Analyzing Resparsification Algorithms

• Rasmus Kyng
• Jakub Pachocki
• Richard Peng
• Sushant Sachdeva

A spectral sparsifier of a graph G is a sparser graph H that approximately preserves the quadratic form of G, i. e. , for all vectors x, x T L Gx ≈ x T L H x, where L G and L H denote the respective graph Laplacians. Spectral sparsifiers generalize cut sparsifiers, and have found many applications in designing graph algorithms. In recent years, there has been interest in computing spectral sparsifiers in semi-streaming and dynamic settings. Natural algorithms in these settings often involve repeated sparsification of a graph, and in turn accumulation of errors across these steps. We present a framework for analyzing algorithms that perform repeated sparsifications that only incur error corresponding to a single sparsification step, leading to better results for many of these reseparsification based algorithms. As an application, we show how to maintain a spectral sparsifier in the semi-streaming setting: We present a simple algorithm that, for a graph G on n vertices and m edges, computes a spectral sparsifier of G with O ( n log n ) edges in a single pass over G, using only O ( n log n ) space, and O ( m log 2 n ) total time. This improves on previous best semi-streaming algorithms for both spectral and cut sparsifiers by a factor of log n in both space and runtime. The algorithm also extends to semi-streaming row sampling for general PSD matrices. As another application, we use this framework to combine a spectral sparsification algorithm by Koutis with improved spanner constructions to give a parallel algorithm for constructing O ( n log 2 n log log n ) sized spectral sparsifiers in O ( m log 2 n log log n ) time. This is the best combinatorial graph sparsification algorithm to date, and the size of the sparsifiers produced is only a factor log n log log n more than ones produced by numerical routines.

STOC Conference 2017 Conference Paper

Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs

• Michael B. Cohen
• Jonathan A. Kelner
• John Peebles
• Richard Peng
• Anup B. Rao
• Aaron Sidford
• Adrian Vladu

In this paper, we begin to address the longstanding algorithmic gap between general and reversible Markov chains. We develop directed analogues of several spectral graph-theoretic tools that had previously been available only in the undirected setting, and for which it was not clear that directed versions even existed. In particular, we provide a notion of approximation for directed graphs, prove sparsifiers under this notion always exist, and show how to construct them in almost linear time. Using this notion of approximation, we design the first almost-linear-time directed Laplacian system solver, and, by leveraging the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS '16], we also obtain almost-linear-time algorithms for computing the stationary distribution of a Markov chain, computing expected commute times in a directed graph, and more. For each problem, our algorithms improve the previous best running times of O (( nm 3/4 + n 2/3 m ) log O (1) ( n κ ε -1 )) to O (( m + n 2 O (√log n loglog n ) ) log O (1) ( n κε -1 )) where n is the number of vertices in the graph, m is the number of edges, κ is a natural condition number associated with the problem, and ε is the desired accuracy. We hope these results open the door for further studies into directed spectral graph theory, and that they will serve as a stepping stone for designing a new generation of fast algorithms for directed graphs.

FOCS Conference 2017 Conference Paper

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

• David Durfee
• John Peebles
• Richard Peng
• Anup B. Rao

We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilizes this combinatorial connection to bridge between statistical leverage scores/effective resistances and the analysis of random graphs by [Janson, Combinatorics, Probability and Computing `94]. This leads to a routine that in quadratic time, sparsifies a graph down to about n1. 5 edges in ways that preserve both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Cholesky factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. We give an algorithm that computes a (1±δ) approximation to the determinant of any SDDM matrix with constant probability in about n 2 δ -2 time. This is the first routine for graphs that outperforms general-purpose routines for computing determinants of arbitrary matrices. We also give an algorithm that generates in about n 2 δ -2 time a spanning tree of a weighted undirected graph from a distribution with total variation distance of δ from the w-uniform distribution.

SODA Conference 2016 Conference Paper

Approximate Undirected Maximum Flows in O ( m polylog( n )) Time

• Richard Peng

We give the first O ( m polylog( n )) time algorithms for approximating maximum flows in undirected graphs and constructing polylog( n )-quality cut-approximating hierarchical tree decompositions. Our algorithm invokes existing algorithms for these two problems recursively while gradually incorporating size reductions. These size reductions are in turn obtained via ultra-sparsifiers, which are key tools in solvers for symmetric diagonally dominant (SDD) linear systems.

FOCS Conference 2016 Conference Paper

Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More

• Michael B. Cohen
• Jonathan A. Kelner
• John Peebles
• Richard Peng
• Aaron Sidford
• Adrian Vladu

In this paper, we provide faster algorithms for computing variousfundamental quantities associated with random walks on a directedgraph, including the stationary distribution, personalized PageRankvectors, hitting times, and escape probabilities. In particular, ona directed graph with n vertices and m edges, we show how tocompute each quantity in time Õ(m3/4n + mn2/3), wherethe Õ notation suppresses polylog factors in n, the desired accuracy, and the appropriate condition number (i. e. themixing time or restart probability). Our result improves upon the previous fastest running times for these problems, previous results either invoke a general purpose linearsystem solver on a n × n matrix with m non-zero entries, or depend polynomially on the desired error or natural condition numberassociated with the problem (i. e. the mixing time or restart probability). For sparse graphs, we obtain a running time of Õ(n7/4), breaking the O(n2) barrier of the best running time one couldhope to achieve using fast matrix multiplication. We achieve our result by providing a similar running time improvementfor solving directed Laplacian systems, a natural directedor asymmetric analog of the well studied symmetric or undirected Laplaciansystems. We show how to solve such systems in time Õ(m3/4n + mn2/3), and efficiently reduce a broad range of problems to solving Õ(1) directed Laplacian systems on Eulerian graphs. We hope these resultsand our analysis open the door for further study into directedspectral graph theory.

FOCS Conference 2016 Conference Paper

On Fully Dynamic Graph Sparsifiers

• Ittai Abraham
• David Durfee
• Ioannis Koutis
• Sebastian Forster
• Richard Peng

We initiate the study of fast dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-spectral sparsifier with amortized update time poly(log n, ϵ -1 ). Second, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-cut sparsifier with worst-case update time poly(log n, ϵ -1 ). Both sparsifiers have size n · poly(log n, ϵ -1 ). Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a (1 - ϵ)-approximation to the value of the maximum flow in an unweighted, undirected, bipartite graph with amortized update time poly(log n, ϵ -1 ).

NeurIPS Conference 2016 Conference Paper

SPALS: Fast Alternating Least Squares via Implicit Leverage Scores Sampling

• Dehua Cheng
• Richard Peng
• Yan Liu
• Ioakeim Perros

Tensor CANDECOMP/PARAFAC (CP) decomposition is a powerful but computationally challenging tool in modern data analytics. In this paper, we show ways of sampling intermediate steps of alternating minimization algorithms for computing low rank tensor CP decompositions, leading to the sparse alternating least squares (SPALS) method. Specifically, we sample the the Khatri-Rao product, which arises as an intermediate object during the iterations of alternating least squares. This product captures the interactions between different tensor modes, and form the main computational bottleneck for solving many tensor related tasks. By exploiting the spectral structures of the matrix Khatri-Rao product, we provide efficient access to its statistical leverage scores. When applied to the tensor CP decomposition, our method leads to the first algorithm that runs in sublinear time per-iteration and approximates the output of deterministic alternating least squares algorithms. Empirical evaluations of this approach show significantly speedups over existing randomized and deterministic routines for performing CP decomposition. On a tensor of the size 2. 4m by 6. 6m by 92k with over 2 billion nonzeros formed by Amazon product reviews, our routine converges in two minutes to the same error as deterministic ALS.

STOC Conference 2016 Conference Paper

Sparsified Cholesky and multigrid solvers for connection laplacians

• Rasmus Kyng
• Yin Tat Lee
• Richard Peng
• Sushant Sachdeva
• Daniel A. Spielman

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process. We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians---a generalization of Laplacian matrices that arise in many problems in image and signal processing. We also prove that every connection Laplacian has a linear sized approximate inverse. This is an LU factorization with a linear number of nonzero entries that is a strong approximation of the original matrix. Using such a factorization one can solve systems of equations in a connection Laplacian in linear time. Such a factorization was unknown even for ordinary graph Laplacians.

STOC Conference 2015 Conference Paper

L p Row Sampling by Lewis Weights

• Michael B. Cohen
• Richard Peng

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 input sparsity time an A' consisting of about d log d rescaled rows of A such that |Ax| 1 is close to |A'x| 1 for all vectors x. We also show similar results for all L p that give nearly optimal sample bounds in input sparsity time. Our results are based on sampling by "Lewis weights", which can be viewed as statistical leverage scores of a reweighted matrix. We also give an elementary proof of the guarantees of this sampling process for L 1 .

STOC Conference 2014 Conference Paper

An efficient parallel solver for SDD linear systems

• Richard Peng
• Daniel A. Spielman

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. The heart of our algorithm is a construction of a sparse approximate inverse chain for the input matrix: a sequence of sparse matrices whose product approximates its inverse. Whereas other fast algorithms for solving systems of equations in SDD matrices exploit low-stretch spanning trees, our algorithm only requires spectral graph sparsifiers.

SODA Conference 2014 Conference Paper

Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball

• Michael B. Cohen
• Brittany Terese Fasy
• Gary L. Miller
• Amir Nayyeri
• Richard Peng
• Noel Walkington

We present an efficient algorithm for solving a linear system arising from the 1-Laplacian corresponding to a collapsible simplicial complex with a known collapsing sequence. When combined with a result of Chillingworth, our algorithm is applicable to convex simplicial complexes embedded in ℝ 3. The running time of our algorithm is nearly-linear in the size of the complex and is logarithmic on its numerical properties. Our algorithm is based on projection operators and combinatorial steps for transferring between them. The former relies on decomposing flows into circulations and potential flows using fast solvers for graph Laplacians, and the latter relates Gaussian elimination to topological properties of simplicial complexes.

STOC Conference 2014 Conference Paper

Solving SDD linear systems in nearly m log 1/2 n time

• Michael B. Cohen
• Rasmus Kyng
• Gary L. Miller
• Jakub Pachocki
• Richard Peng
• Anup B. Rao
• Shen Chen Xu

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 approach follows the recursive preconditioning framework, which aims to reduce graphs to trees using iterative methods. We improve two key components of this framework: random sampling and tree embeddings. Both of these components are used in a variety of other algorithms, and our approach also extends to the dual problem of computing electrical flows.

SODA Conference 2013 Conference Paper

Approximate Maximum Flow on Separable Undirected Graphs

• Gary L. Miller
• Richard Peng

We present faster algorithms for approximate maximum flow in undirected graphs with good separator structures, such as bounded genus, minor free, and geometric graphs. Given such a graph with n vertices, m edges along with a recursive -vertex separator structure, our algorithm finds an 1 − ∊ approximate maximum flow in time Õ ( m 6/5 poly (∊ −1 )), ignoring poly-logarithmic terms. Similar speedups are also achieved for separable graphs with larger size separators albeit with larger run times. These bounds also apply to image problems in two and three dimensions. Key to our algorithm is an intermediate problem that we term grouped L 2 flow, which exists between maximum flows and electrical flows. Our algorithm also makes use of spectral vertex sparsifiers in order to remove vertices while preserving the energy dissipation of electrical flows. We also give faster spectral vertex sparsification algorithms on well separated graphs, which may be of independent interest.

FOCS Conference 2013 Conference Paper

Fully Dynamic (1+ e)-Approximate Matchings

• Manoj Gupta 0002
• Richard Peng

We present the first data structures that maintain near optimal maximum cardinality and maximum weighted matchings on sparse graphs in sub linear time per update. Our main result is a data structure that maintains a (1+ε) approximation of maximum matching under edge insertions/deletions in worst case Õ(? mε-2) time per update. This improves the 3/2 approximation given by Neiman and Solomon [20] which runs in similar time. The result is based on two ideas. The first is to re-run a static algorithm after a chosen number of updates to ensure approximation guarantees. The second is to judiciously trim the graph to a smaller equivalent one whenever possible. We also study extensions of our approach to the weighted setting, and combine it with known frameworks to obtain arbitrary approximation ratios. For a constant ε and for graphs with edge weights between 1 and N, we design an algorithm that maintains an (1+ε) approximate maximum weighted matching in Õ(? m log N) time per update. The only previous result for maintaining weighted matchings on dynamic graphs has an approximation ratio of 4. 9108, and was shown by An and et al. [2], [3].

FOCS Conference 2013 Conference Paper

Iterative Row Sampling

• Mu Li
• Gary L. Miller
• Richard Peng

There has been significant interest and progress recently in algorithms that solve regression problems involving tall and thin matrices in input sparsity time. Given a n * d matrix where n ≥ d, these algorithms find an approximation with fewer rows, allowing one to solve a poly(d) sized problem instead. In practice, the best performances are often obtained by invoking these routines in an iterative fashion. We show these iterative methods can be adapted to give theoretical guarantees comparable to and better than the current state of the art. Our approaches are based on computing the importances of the rows, known as leverage scores, in an iterative manner. We show that alternating between computing a short matrix estimate and finding more accurate approximate leverage scores leads to a series of geometrically smaller instances. This gives an algorithm whose runtime is input sparsity plus an overhead comparable to the cost of solving a regression problem on the smaller approximation. Our results build upon the close connection between randomized matrix algorithms, iterative methods, and graph sparsification.

STOC Conference 2012 Conference Paper

Faster approximate multicommodity flow using quadratically coupled flows

• Jonathan A. Kelner
• Gary L. Miller
• Richard Peng

The maximum multicommodity flow problem is a natural generalization of the maximum flow problem to route multiple distinct flows. Obtaining a 1-ε approximation to the multicommodity flow problem on graphs is a well-studied problem. In this paper we present an adaptation of recent advances in single-commodity flow algorithms to this problem. As the underlying linear systems in the electrical problems of multicommodity flow problems are no longer Laplacians, our approach is tailored to generate specialized systems which can be preconditioned and solved efficiently using Laplacians. Given an undirected graph with m edges and k commodities, we give algorithms that find 1-ε approximate solutions to the maximum concurrent flow problem and maximum weighted multicommodity flow problem in time O(m 4/3 poly(k,ε -1 )).

FOCS Conference 2011 Conference Paper

A Nearly-m log n Time Solver for SDD Linear Systems

• Ioannis Koutis
• Gary L. Miller
• Richard Peng

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 a vector b such that Ax̅ = b for some (unknown) vector x̅, our algorithm computes a vector x such that ∥x-x̅∥ A ≤ϵ∥x̅∥ A 1 in time Õ (m log n log (1/ϵ)) 2. The solver utilizes in a standard way a 'preconditioning' chain of progressively sparser graphs. To claim the faster running time we make a two-fold improvement in the algorithm for constructing the chain. The new chain exploits previously unknown properties of the graph sparsification algorithm given in [Koutis, Miller, Peng, FOCS 2010], allowing for stronger preconditioning properties. We also present an algorithm of independent interest that constructs nearly-tight low-stretch spanning trees in time Õ (m log n), a factor of O (log n) faster than the algorithm in [Abraham, Bartal, Neiman, FOCS 2008]. This speedup directly reflects on the construction time of the preconditioning chain.

SODA Conference 2011 Conference Paper

Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge Decomposition

• Gary L. Miller
• Richard Peng
• Russell Schwartz
• Charalampos E. Tsourakakis

We consider the problem of approximating a signal P with another signal F consisting of a few piecewise constant segments. This problem arises naturally in applications including databases (e. g. , histogram construction), speech recognition, computational biology (e. g. , denoising aCGH data) and many more. Specifically, let P = (P 1, P 2, …, P n ), P i ∊ ℝ for all i, be a signal and let C be a constant. Our goal is to find a function F: [ n ] → ℝ which optimizes the following objective function: The above optimization problem reduces to solving the following recurrence, which can be done using dynamic programming in O ( n 2 ) time: This recurrence arises naturally in several applications where one wants to approximate a given signal P with a signal F which ideally consists of few piecewise constant segments. Such applications include histogram construction in databases, determining DNA copy numbers in cancer cells from micro-array data, speech recognition, data mining and many others. In this work we present two new techniques for optimizing dynamic programming that can handle cost functions not treated by other standard methods. The basis of our first algorithm is the definition of a constant-shifted variant of the objective function that can be efficiently approximated using state of the art methods for range searching. Our technique approximates the optimal value of our objective function within additive ∊ error and runs in time, where δ is an arbitrarily small positive constant and. The second algorithm we provide solves a similar recurrence that's within a multiplicative factor of (1+∊) and runs in O ( n log n /∊). The new technique introduced by our algorithm is the decomposition of the initial problem into a small (logarithmic) number of Monge optimization subproblems which we can speed up using existing techniques.

FOCS Conference 2010 Conference Paper

Approaching Optimality for Solving SDD Linear Systems

• Ioannis Koutis
• Gary L. Miller
• Richard Peng

We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k, produces an incremental sparsifier G with n-1+m/k edges, such that the condition number of G with G is bounded above by Õ(k log 2 n), with probability 1-p. The algorithm runs in time Õ((m log n + n log n) log(1/p)). As a result, we obtain an algorithm that on input of an n × n symmetric diagonally dominant matrix A with m non-zero entries and a vector b, computes a vector x satisfying ||x-A + b||A + b||A, in expected time Õ(m log 2 n log(1/ϵ)). The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to a recursive preconditioned Chebyshev iteration.