24 citations · 151 across the 43 of their papers we have counts for
5 papers · 2 filters
A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs
Lawrence Li, Sushant Sachdeva
We demonstrate that for expander graphs, for all there exists a data structure of size which can be used to return -approximations to effe…
Fast Algorithms for -Regression
Deeksha Adil, Rasmus Kyng, Richard Peng +1
The -norm regression problem is a classic problem in optimization with wide ranging applications in machine learning and theoretical computer science. The goal is to comput…
A Simple Framework for Finding Balanced Sparse Cuts via APSP
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg +1
We present a very simple and intuitive algorithm to find balanced sparse cuts in a graph via shortest-paths. Our algorithm combines a new multiplicative-weights framework for solvi…
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
Sally Dong, Yu Gao, Gramoz Goranci +4
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 fo…
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
Li Chen, Rasmus Kyng, Yang P. Liu +3
We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral demands, costs, and capacities in…