24 citations · 58 across the 19 of their papers we have counts for
23 papers
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
Jan van den Brand, Li Chen, Rasmus Kyng +5
We provide an algorithm which, with high probability, maintains a -approximate maximum flow on an undirected graph undergoing -edge additions in amortized $m^{o(1)} ε^{-3…
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…
Weil-Poincaré series and topology of collections of valuations on rational double points
A. Campillo, F. Delgado, S. M. Gusein-Zade
Earlier it was described to which extent the Alexander polynomial in several variables of an algebraic link in the Poincaré sphere determines the topology of the link. It was shown…
Improved Iteration Complexities for Overconstrained -Norm Regression
Arun Jambulapati, Yang P. Liu, Aaron Sidford
In this paper we obtain improved iteration complexities for solving regression. We provide methods which given any full-rank with…
Online Edge Coloring via Tree Recurrences and Correlation Decay
Janardhan Kulkarni, Yang P. Liu, Ashwin Sah +2
We give an online algorithm that with high probability computes a edge coloring on a graph with maximum degree under online…
Arithmetic Progressions in Sumsets of Sparse Sets
Noga Alon, Ryan Alweiss, Yang P. Liu +2
A set of positive integers is \emph{log-sparse} if there is an absolute constant so that for any positive integer the sequence contains at most…
A Gaussian fixed point random walk
Yang P. Liu, Ashwin Sah, Mehtaab Sawhney
In this note, we design a discrete random walk on the real line which takes steps (and one with steps in ) where at least of the signs are i…
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
Yu Gao, Yang P. Liu, Richard Peng
We give an algorithm for computing exact maximum flows on graphs with edges and integer capacities in the range in $\widetilde{O}(m^{\frac{3}{2} - \frac{1}{328}} \log…
Minor Sparsifiers and the Distributed Laplacian Paradigm
Sebastian Forster, Gramoz Goranci, Yang P. Liu +3
We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrice…
Vertex Sparsification for Edge Connectivity in Polynomial Time
Yang P. Liu
An important open question in the area of vertex sparsification is whether -approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. T…
Vertex Sparsification for Edge Connectivity
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit +5
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether -approximate cut-prese…
Discrepancy Minimization via a Self-Balancing Walk
Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney
We study discrepancy minimization for vectors in under various settings. The main result is the analysis of a new simple random process in multiple dimensions throug…
Faster Divergence Maximization for Faster Maximum Flow
Yang P. Liu, Aaron Sidford
In this paper we provide an algorithm which given any -edge -vertex directed graph with integer capacities at most computes a maximum - flow for any vertices an…
Faster Energy Maximization for Faster Maximum Flow
Yang P. Liu, Aaron Sidford
In this paper we provide an algorithm which given any -edge -vertex directed graph with integer capacities at most computes a maximum - flow for any vertices an…
Vertex Sparsifiers for c-Edge Connectivity
Yang P. Liu, Richard Peng, Mark Sellke
We show the existence of O(f(c)k) sized vertex sparsifiers that preserve all edge-connectivity values up to c between a set of k terminal vertices, where f(c) is a function that on…
On the upper tail problem for random hypergraphs
Yang P. Liu, Yufei Zhao
The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an Erdős--Rényi random graph exceeds its expectation b…
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
Brian Axelrod, Yang P. Liu, Aaron Sidford
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given a…
Constant Girth Approximation for Directed Graphs in Subquadratic Time
Shiri Chechik, Yang P. Liu, Omer Rotem +1
In this paper we provide a time algorithm that computes a -multiplicative approximation of the girth of a -node -edge directed graph with non-negati…
Parallel Reachability in Almost Linear Work and Square Root Depth
Arun Jambulapati, Yang P. Liu, Aaron Sidford
In this paper we provide a parallel algorithm that given any -node -edge directed graph and source vertex computes all vertices reachable from with wor…
Short Cycles via Low-Diameter Decompositions
Yang P. Liu, Sushant Sachdeva, Zejun Yu
We present improved algorithms for short cycle decomposition of a graph. Short cycle decompositions were introduced in the recent work of Chu et al, and were used to make progress…