10 citations · 22 across the 12 of their papers we have counts for
14 papers
Rectilinear Matching to the Integer Grid in Nearly-Linear Time
Yu Gao
Rectilinear matching to the integer grid asks to assign each of points in to a distinct point of , minimizing total movement. The main diffi…
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…
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…
Hardness of Graph-Structured Algebraic and Symbolic Problems
Jingbang Chen, Yu Gao, Yufan Huang +2
In this paper, we study the hardness of solving graph-structured linear systems with coefficients over a finite field and over a polynomial ring $\mathbb{F}[x_1,\ldo…
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…
A Study of Performance of Optimal Transport
Yihe Dong, Yu Gao, Richard Peng +2
We investigate the problem of efficiently computing optimal transport (OT) distances, which is equivalent to the node-capacitated minimum cost maximum flow problem in a bipartite g…
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex
Yu Gao, Jason Li, Danupon Nanongkai +3
We study deterministic algorithms for computing graph cuts, with focus on two fundamental problems: balanced sparse cut and -vertex connectivity for small ($k=O(\polylog n)$…
Flowless: Extracting Densest Subgraphs Without Flow Computations
Digvijay Boob, Yu Gao, Richard Peng +4
We propose a simple and computationally efficient method for dense subgraph discovery, which is a classic problem both in theory and in practice. It is well known that dense subgra…
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
Julia Chuzhoy, Yu Gao, Jason Li +3
We consider the classical Minimum Balanced Cut problem: given a graph , compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number…
Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee, Yu Gao, Gramoz Goranci +1
We study \emph{dynamic} algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals of our choice. Such objects preserve pairwise resist…
Efficient Second-Order Shape-Constrained Function Fitting
David Durfee, Yu Gao, Anup B. Rao +1
We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted- norm. We give a single algorithm that works for a va…
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Timothy Chu, Yu Gao, Richard Peng +3
We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collec…
Fully Dynamic Effective Resistances
David Durfee, Yu Gao, Gramoz Goranci +1
In this paper we consider the \emph{fully-dynamic} All-Pairs Effective Resistance problem, where the goal is to maintain effective resistances on a graph among any pair of quer…
Nearly Tight Bounds for Sandpile Transience on the Grid
David Durfee, Matthew Fahrbach, Yu Gao +1
We use techniques from the theory of electrical networks to give nearly tight bounds for the transience class of the Abelian sandpile model on the two-dimensional grid up to polylo…