16 citations · 61 across the 32 of their papers we have counts for
14 papers · 1 filter
Uncertainty Quantification for Gradient and Accelerated Gradient Descent Methods on Strongly Convex Functions
Conor McMeel, Panos Parpas
We consider the problem of minimizing a strongly convex function that depends on an uncertain parameter . The uncertainty in the objective function means that the optimum, $x^*(…
Minimum Cuts in Directed Graphs via Partial Sparsification
Ruoxu Cen, Jason Li, Danupon Nanongkai +3
We give an algorithm to find a minimum cut in an edge-weighted directed graph with vertices and edges in time. This improves on the 30 y…
Augmenting Edge Connectivity via Isolating Cuts
Ruoxu Cen, Jason Li, Debmalya Panigrahi
We give an algorithm for augmenting the edge connectivity of an undirected graph by using the isolating cuts framework (Li and Panigrahi, FOCS '20). Our algorithm uses poly-logarit…
Approximate Gomory-Hu Tree Is Faster Than Max-Flows
Jason Li, Debmalya Panigrahi
The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reporting mincuts (and by duality, the values of maxflows) for all pairs of ver…
Matroid-Based TSP Rounding for Half-Integral Solutions
Anupam Gupta, Euiwoong Lee, Jason Li +3
We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-1.5 factor. Such a rounding algorithm was recently given…
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
Amir Abboud, Robert Krauthgamer, Jason Li +3
In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all pairs of vertices in an undirected graph can be solved using on…