24 citations · 108 across the 21 of their papers we have counts for
23 papers · 1 filter
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…
Computing Lewis Weights to High Precision
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan +1
We present an algorithm for computing approximate Lewis weights to high precision. Given a full-rank with and a scalar…
Tutorial on the Robust Interior Point Method
Yin Tat Lee, Santosh S. Vempala
We give a short, self-contained proof of the interior point method and its robust version.
Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
Yin Tat Lee, Ruoqi Shen, Kevin Tian
We give lower bounds on the performance of two of the most popular sampling methods in practice, the Metropolis-adjusted Langevin algorithm (MALA) and multi-step Hamiltonian Monte…
Numerical Composition of Differential Privacy
Sivakanth Gopi, Yin Tat Lee, Lukas Wutschitz
We give a fast algorithm to optimally compose privacy guarantees of differentially private (DP) algorithms to arbitrary accuracy. Our method is based on the notion of privacy loss…
Structured Logconcave Sampling with a Restricted Gaussian Oracle
Yin Tat Lee, Ruoqi Shen, Kevin Tian
We give algorithms for sampling several structured logconcave families to high accuracy. We further develop a reduction framework, inspired by proximal point methods in convex opti…