24 citations · 58 across the 19 of their papers we have counts for
4 papers · 1 filter
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
Arun Jambulapati, Yang P. Liu, Aaron Sidford
We present an algorithm that given any -vertex, -edge, rank hypergraph constructs a spectral sparsifier with hyperedges in nearly-li…
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…
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…
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
Nima Anari, Yang P. Liu, Thuy-Duong Vuong
We design fast algorithms for repeatedly sampling from strongly Rayleigh distributions, which include random spanning tree distributions and determinantal point processes. For a gr…