3 citations · 9 across the 9 of their papers we have counts for
6 papers · 1 filter
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan +3
We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen kno…
Fast Algorithms for Separable Linear Programs
Sally Dong, Gramoz Goranci, Lawrence Li +2
In numerical linear algebra, considerable effort has been devoted to obtaining faster algorithms for linear systems whose underlying matrices exhibit structural properties. A promi…
Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
Sally Dong, Guanghao Ye
We present an algorithm for min-cost flow in graphs with vertices and edges, given a tree decomposition of width and size , and polynomially bounded, integral edge c…
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…
A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
Sally Dong, Yin Tat Lee, Guanghao Ye
Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms in various communities including combinatorics, integer-linear p…
Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time
Jerry Li, Guanghao Ye
Robust covariance estimation is the following, well-studied problem in high dimensional statistics: given samples from a -dimensional Gaussian $\mathcal{N}(\boldsymbol{0}, Σ…