12 papers
On the Streaming Complexity of Expander Decomposition
Yu Chen, Michael Kapralov, Mikhail Makarov +1
In this paper we study the problem of finding -expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions…
Query Complexity of the Metric Steiner Tree Problem
Yu Chen, Sanjeev Khanna, Zihan Tan
We study the query complexity of the metric Steiner Tree problem, where we are given an metric on a set of vertices along with a set of termina…
On Weighted Graph Sparsification by Linear Sketching
Yu Chen, Sanjeev Khanna, Huan Li
A seminal work of [Ahn-Guha-McGregor, PODS'12] showed that one can compute a cut sparsifier of an unweighted undirected graph by taking a near-linear number of linear measurements…
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
Yu Chen, Sanjeev Khanna, Zihan Tan
We consider the design of sublinear space and query complexity algorithms for estimating the cost of a minimum spanning tree (MST) and the cost of a minimum traveling salesman (TSP…
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection
Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna
Submodular function minimization (SFM) and matroid intersection are fundamental discrete optimization problems with applications in many fields. It is well known that both of these…
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
Yu Chen, Sanjeev Khanna, Ansh Nagda
The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Bencz…