2 citations · 3 across the 7 of their papers we have counts for
8 papers
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…
Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity
Sally Dong, Thomas Rothvoss
We show that any bounded integral function with rank has deterministic communication complexity $Δ^{O(Δ)} \cdot \sqrt{r} \cdot \log r…
Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity
Sally Dong, Haotian Jiang, Yin Tat Lee +2
Many fundamental problems in machine learning can be formulated by the convex program \[ \min_{θ\in R^d}\ \sum_{i=1}^{n}f_{i}(θ), \] where each is a convex, Lipschitz functio…
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…
Computing Circle Packing Representations of Planar Graphs
Sally Dong, Yin Tat Lee, Kent Quanrud
The Circle Packing Theorem states that every planar graph can be represented as the tangency graph of a family of internally-disjoint circles. A well-known generalization is the Pr…
Improved bounds for Rota's Basis Conjecture
Sally Dong, Jim Geelen
We prove that, if are disjoint bases of a rank- matroid, then there are at least disjoint transversals of $(…