93 citations · 537 across the 73 of their papers we have counts for
8 papers · 1 filter
A Generalized Cheeger Inequality
Ioannis Koutis, Gary Miller, Richard Peng
The generalized conductance between two graphs and on the same vertex set is defined as the ratio $$ ϕ(G,H) = \min_{S\subseteq V} \frac{cap_G(S,\bar{S})}{ cap_…
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 -by- matrix …
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 deco…
Partitioning Well-Clustered Graphs: Spectral Clustering Works!
Richard Peng, He Sun, Luca Zanetti
In this paper we study variants of the widely used spectral clustering that partitions a graph into k clusters by (1) embedding the vertices of a graph into a low-dimensional space…
Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models
Dehua Cheng, Yu Cheng, Yan Liu +2
Motivated by a sampling problem basic to computational statistical inference, we develop a nearly optimal algorithm for a fundamental problem in spectral graph theory and numerical…
Uniform Sampling for Matrix Approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco +3
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 a…