S. Khanna

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 $n \times n$ metric on a set $V$ of vertices along with a set $T \subseteq V$ of $k$ 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…

cs.DS2022★ 2 cited

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…

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…

cs.DS2022★ 1 cited

New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS

Soheil Behnezhad, Sanjeev Khanna

We study the maximum matching problem in fully dynamic graphs: a graph is undergoing both edge insertions and deletions, and the goal is to efficiently maintain a large matching af…

cs.DS2021

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…

cs.DS2021

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…

Near-linear Size Hypergraph Cut Sparsifiers

Yu Chen, Sanjeev Khanna, Ansh Nagda

Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cu…

Graph Connectivity and Single Element Recovery via Linear and OR Queries

Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna

We study the problem of finding a spanning forest in an undirected, $n$ -vertex multi-graph under two basic query models. One is the Linear query model which are linear measurements…

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs

Anindya De, Sanjeev Khanna, Huan Li +1

We give the first polynomial-time approximation scheme (PTAS) for the stochastic load balancing problem when the job sizes follow Poisson distributions. This improves upon the 2-ap…

Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation

Yu Chen, Sampath Kannan, Sanjeev Khanna

We consider the problem of designing sublinear time algorithms for estimating the cost of a minimum metric traveling salesman (TSP) tour. Specifically, given access to a $n \times…

Near-Perfect Recovery in the One-Dimensional Latent Space Model

Yu Chen, Sampath Kannan, Sanjeev Khanna

Suppose a graph $G$ is stochastically created by uniformly sampling vertices along a line segment and connecting each pair of vertices with a probability that is a known decreasing…

cs.DS2019

A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems

Julia Chuzhoy, Sanjeev Khanna

We study the vertex-decremental Single-Source Shortest Paths (SSSP) problem: given an undirected graph $G = (V, E)$ with lengths $ℓ (e) \geq 1$ on its edges and a source vertex $s$ ,…

cs.DS2019

Polynomial Pass Lower Bounds for Graph Streaming Algorithms

Sepehr Assadi, Yu Chen, Sanjeev Khanna

We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instan…

cs.DS2018★ 31 cited

A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling

Sepehr Assadi, Michael Kapralov, Sanjeev Khanna

In the subgraph counting problem, we are given a input graph $G (V, E)$ and a target graph $H$ ; the goal is to estimate the number of occurrences of $H$ in $G$ . Our focus here is on…

Stochastic Submodular Cover with Limited Adaptivity

Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna

In the submodular cover problem, we are given a non-negative monotone submodular function $f$ over a ground set $E$ of items, and the goal is to choose a smallest subset $S \subset…

cs.DS2018★ 3 cited

Testing Graph Clusterability: Algorithms and Lower Bounds

Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna +2

We consider the problem of testing graph cluster structure: given access to a graph $G = (V, E)$ , can we quickly determine whether the graph can be partitioned into a few clusters wi…

Sublinear Algorithms for $(Δ + 1)$ Vertex Coloring

Sepehr Assadi, Yu Chen, Sanjeev Khanna

Any graph with maximum degree $Δ$ admits a proper vertex coloring with $Δ + 1$ colors that can be found via a simple sequential greedy algorithm in linear time and space. But can on…

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling

Deeparnab Chakrabarty, Sanjeev Khanna

Given a non-negative $n \times m$ real matrix $A$ , the {\em matrix scaling} problem is to determine if it is possible to scale the rows and columns so that each row and each column…