research
∙
03/01/2023
Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights
This paper presents parallel and distributed algorithms for single-sourc...
share
research
∙
02/20/2023
Fast Algorithms via Dynamic-Oracle Matroids
We initiate the study of matroid problems in a new oracle model called d...
research
∙
02/12/2023
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Given a simple n-vertex, m-edge graph G undergoing edge insertions and d...
research
∙
08/04/2022
Nearly Optimal Communication and Query Complexity of Bipartite Matching
We settle the complexities of the maximum-cardinality bipartite matching...
research
∙
05/30/2022
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
In the k-edge-connected spanning subgraph (kECSS) problem, our goal is t...
research
∙
03/07/2022
Negative-Weight Single-Source Shortest Paths in Near-linear Time
We present a randomized algorithm that computes single-source shortest p...
research
∙
03/01/2022
Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time
In this paper, we introduce a robust notion of (1+ϵ)-approximate (s, t)-...
research
∙
01/14/2022
Cut query algorithms with star contraction
We study the complexity of determining the edge connectivity of a simple...
research
∙
11/17/2021
Minimum Cuts in Directed Graphs via Partial Sparsification
We give an algorithm to find a minimum cut in an edge-weighted directed ...
research
∙
04/16/2021
Minimum Cuts in Directed Graphs via √(n) Max-Flows
We give an algorithm to find a mincut in an n-vertex, m-edge weighted di...
research
∙
03/31/2021
Vertex Connectivity in Poly-logarithmic Max-flows
The vertex connectivity of an m-edge n-vertex undirected graph is the sm...
research
∙
03/29/2021
A Note on Isolating Cut Lemma for Submodular Function Minimization
It has been observed independently by many researchers that the isolatin...
research
∙
02/12/2021
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs
We present the first work-optimal polylogarithmic-depth parallel algorit...
research
∙
02/10/2021
Breaking the Quadratic Barrier for Matroid Intersection
The matroid intersection problem is a fundamental problem that has been ...
research
∙
11/16/2020
Faster connectivity in low-rank hypergraphs via expander decomposition
We design an algorithm for computing connectivity in hypergraphs which r...
research
∙
09/03/2020
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
We present an Õ(m+n^1.5)-time randomized algorithm for maximum cardinali...
research
∙
04/20/2020
Distributed Weighted Min-Cut in Nearly-Optimal Time
Minimum-weight cut (min-cut) is a basic measure of a network's connectiv...
research
∙
04/17/2020
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Designing dynamic graph algorithms against an adaptive adversary is a ma...
research
∙
02/25/2020
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
In the dynamic minimum set cover problem, a challenge is to minimize the...
research
∙
02/25/2020
An Improved Algorithm for Dynamic Set Cover
We consider the minimum set cover problem in a dynamic setting. Here, we...
research
∙
01/07/2020
Equivalence Classes and Conditional Hardness in Massively Parallel Computations
The Massively Parallel Computation (MPC) model serves as a common abstra...
research
∙
01/02/2020
Coarse-Grained Complexity for Dynamic Algorithms
To date, the only way to argue polynomial lower bounds for dynamic algor...
research
∙
11/05/2019
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Consider the following 2-respecting min-cut problem. Given a weighted g...
research
∙
10/31/2019
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Consider the following "local" cut-detection problem in a directed graph...
research
∙
10/17/2019
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
We consider the classical Minimum Balanced Cut problem: given a graph G,...
research
∙
10/17/2019
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex
We study deterministic algorithms for computing graph cuts, with focus o...
research
∙
09/25/2019
A New Deterministic Algorithm for Dynamic Set Cover
We present a deterministic dynamic algorithm for maintaining a (1+ϵ)f-ap...
research
∙
09/24/2019
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
Consider the following distance query for an n-node graph G undergoing e...
research
∙
05/14/2019
Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries
We present a new, simple, algorithm for the local vertex connectivity pr...
research
∙
05/13/2019
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
The dynamic matrix inverse problem is to maintain the inverse of a matri...
research
∙
04/09/2019
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Vertex connectivity a classic extensively-studied problem. Given an inte...
research
∙
04/08/2019
Distributed Edge Connectivity in Sublinear Time
We present the first sublinear-time algorithm for a distributed message-...
research
∙
11/08/2018
Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
In the distributed all-pairs shortest paths problem (APSP), every node ...
research
∙
11/12/2017
Dynamic Algorithms for Graph Coloring
We design fast dynamic algorithms for proper vertex and edge colorings i...
research
∙
11/03/2017
A Faster Distributed Single-Source Shortest Paths Algorithm
We devise new algorithms for the single-source shortest paths problem in...
research
∙
08/14/2017
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
We consider questions that arise from the intersection between the areas...
research
∙
08/11/2017