93 citations · 253 across the 24 of their papers we have counts for
17 papers · 1 filter
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…
An Empirical Study of Cycle Toggling Based Laplacian Solvers
Kevin Deweese, John R. Gilbert, Gary Miller +3
We study the performance of linear solvers for graph Laplacians based on the combinatorial cycle adjustment methodology proposed by [Kelner-Orecchia-Sidford-Zhu STOC-13]. The appro…
Geometric Median in Nearly Linear Time
Michael B. Cohen, Yin Tat Lee, Gary Miller +2
In this paper we provide faster algorithms for solving the geometric median problem: given points in compute a point that minimizes the sum of Euclidean distan…
Routing under Balance
Alina Ene, Gary Miller, Jakub Pachocki +1
We introduce the notion of balance for directed graphs: a weighted directed graph is -balanced if for every cut , the total weight of edges going from to $V\s…
Stretching Stretch
Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki +2
We give a generalized definition of stretch that simplifies the efficient construction of low-stretch embeddings suitable for graph algorithms. The generalization, based on discoun…