93 citations · 537 across the 73 of their papers we have counts for
68 papers · 1 filter
Simpler Analyses of Union-Find
Zhiyi Huang, Chris Lambert, Zipei Nie +1
We analyze union-find using potential functions motivated by continuous algorithms, and give alternate proofs of the , , , and $O(α(n))…
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, -norm regression, and linear programming (LP). State-of-t…
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…
Exponential Convergence of Sinkhorn Under Regularization Scheduling
Jingbang Chen, Li Chen, Yang P. Liu +2
In 2013, Cuturi [Cut13] introduced the Sinkhorn algorithm for matrix scaling as a method to compute solutions to regularized optimal transport problems. In this paper, aiming at a…
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…