24 citations · 58 across the 19 of their papers we have counts for
6 papers · 1 filter
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…