research
∙
11/07/2022
Query Complexity of the Metric Steiner Tree Problem
We study the query complexity of the metric Steiner Tree problem, where ...
share
research
∙
09/16/2022
On Weighted Graph Sparsification by Linear Sketching
A seminal work of [Ahn-Guha-McGregor, PODS'12] showed that one can compu...
research
∙
07/19/2022
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
We present a new approach for finding matchings in dense graphs by build...
research
∙
03/28/2022
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
We consider the design of sublinear space and query complexity algorithm...
research
∙
01/09/2022
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS
We study the maximum matching problem in fully dynamic graphs: a graph i...
research
∙
11/14/2021
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection
Submodular function minimization (SFM) and matroid intersection are fund...
research
∙
06/18/2021
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
The problem of sparsifying a graph or a hypergraph while approximately p...
research
∙
09/10/2020
Near-linear Size Hypergraph Cut Sparsifiers
Cuts in graphs are a fundamental object of study, and play a central rol...
research
∙
07/12/2020
Graph Connectivity and Single Element Recovery via Linear and OR Queries
We study the problem of finding a spanning forest in an undirected, n-ve...
research
∙
06/23/2020
An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs
We give the first polynomial-time approximation scheme (PTAS) for the st...
research
∙
06/09/2020
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
We consider the problem of designing sublinear time algorithms for estim...
research
∙
06/08/2020
Near-Perfect Recovery in the One-Dimensional Latent Space Model
Suppose a graph G is stochastically created by uniformly sampling vertic...
research
∙
06/01/2019
Network Formation under Random Attack and Probabilistic Spread
We study a network formation game where agents receive benefits by formi...
research
∙
05/27/2019
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems
We study the vertex-decremental Single-Source Shortest Paths (SSSP) prob...
research
∙
04/09/2019
Polynomial Pass Lower Bounds for Graph Streaming Algorithms
We present new lower bounds that show that a polynomial number of passes...
research
∙
11/19/2018
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
In the subgraph counting problem, we are given a input graph G(V, E) and...
research
∙
10/31/2018
Stochastic Submodular Cover with Limited Adaptivity
In the submodular cover problem, we are given a non-negative monotone su...
research
∙
08/14/2018
Testing Graph Clusterability: Algorithms and Lower Bounds
We consider the problem of testing graph cluster structure: given access...
research
∙
07/24/2018
Sublinear Algorithms for (Δ+ 1) Vertex Coloring
Any graph with maximum degree Δ admits a proper vertex coloring with Δ +...
research
∙
01/09/2018
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem
We study the maximum k-set coverage problem in the following distributed...
research
∙
01/09/2018