research
∙
07/17/2023
Fully Dynamic Matching: (2-√(2))-Approximation in Polylog Update Time
We study maximum matchings in fully dynamic graphs, which are graphs tha...
share
research
∙
05/02/2023
Streaming Edge Coloring with Asymptotically Optimal Colors
Given a graph G, an edge-coloring is an assignment of colors to edges of...
research
∙
05/01/2023
Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation
We study the robust communication complexity of maximum matching. Edges ...
research
∙
01/13/2023
Sublinear Algorithms for TSP via Path Covers
We study sublinear time algorithms for the traveling salesman problem (T...
research
∙
11/29/2022
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Sublinear time algorithms for approximating maximum matching size have l...
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
∙
07/15/2022
Dynamic Algorithms for Maximum Matching Size
We study fully dynamic algorithms for maximum matching. This is a well-s...
research
∙
06/27/2022
Beating Greedy Matching in Sublinear Time
We study sublinear time algorithms for estimating the size of maximum ma...
research
∙
05/07/2022
Almost 3-Approximate Correlation Clustering in Constant Rounds
We study parallel algorithms for correlation clustering. Each pair among...
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
∙
12/10/2021
Stochastic Vertex Cover with Few Queries
We study the minimum vertex cover problem in the following stochastic se...
research
∙
10/12/2021
Improved Analysis of EDCS via Gallai-Edmonds Decomposition
In this note, we revisit the edge-degree constrained subgraph (EDCS) int...
research
∙
06/05/2021
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
We present a near-tight analysis of the average "query complexity" – à l...
research
∙
02/13/2021
Beating Two-Thirds For Random-Order Streaming Matching
We study the maximum matching problem in the random-order semi-streaming...
research
∙
09/24/2020
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
We study fundamental graph problems such as graph connectivity, minimum ...
research
∙
04/18/2020
Stochastic Weighted Matching: (1-ε) Approximation
Let G=(V, E) be a given edge-weighted graph and let its realizationG be...
research
∙
02/27/2020
Stochastic Matching with Few Queries: (1-ε) Approximation
Suppose that we are given an arbitrary graph G=(V, E) and know that each...
research
∙
11/05/2019
Fully Dynamic Matching: Beating 2-Approximation in Δ^ε Update Time
In fully dynamic graphs, we know how to maintain a 2-approximation of ma...
research
∙
10/11/2019
Near-Optimal Massively Parallel Graph Connectivity
Identifying the connected components of a graph, apart from being a fund...
research
∙
09/08/2019
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
We present the first algorithm for maintaining a maximal independent set...
research
∙
05/18/2019
Massively Parallel Computation via Remote Memory Access
We introduce the Adaptive Massively Parallel Computation (AMPC) model, w...
research
∙
01/14/2019
Optimal Strategies of Blotto Games: Beyond Convexity
The Colonel Blotto game, first introduced by Borel in 1921, is a well-st...
research
∙
01/11/2019
Exponentially Faster Massively Parallel Maximal Matching
The study of graph problems in the Massively Parallel Computations (MPC)...
research
∙
11/08/2018
Stochastic Matching with Few Queries: New Algorithms and Tools
We consider the following stochastic matching problem on both weighted a...
research
∙
09/11/2018
Massively Parallel Dynamic Programming on Trees
Dynamic programming is a powerful technique that is, unfortunately, ofte...
research
∙
07/17/2018
Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
The success of massively parallel computation (MPC) paradigms such as Ma...
research
∙
02/28/2018
Brief Announcement: Semi-MapReduce Meets Congested Clique
Graph problems are troublesome when it comes to MapReduce. Typically, to...
research
∙
10/29/2017