279 citations · 500 across the 42 of their papers we have counts for
52 papers
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…
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna +1
We present a new approach for finding matchings in dense graphs by building on Szemerédi's celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improveme…
Sublinear Algorithms for Hierarchical Clustering
Arpit Agarwal, Sanjeev Khanna, Huan Li +1
Hierarchical clustering over graphs is a fundamental task in data mining and machine learning with applications in domains such as phylogenetics, social network analysis, and infor…
A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits
Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil
The stochastic -armed bandit problem has been studied extensively due to its applications in various domains ranging from online advertising to clinical trials. In practice howe…
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…