research
∙
08/09/2023
Deterministic k-Vertex Connectivity in k^2 Max-flows
An n-vertex m-edge graph is k-vertex connected if it cannot be disconnec...
share
research
∙
06/30/2023
Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k
We give the first almost-linear time algorithm for computing the maximal...
research
∙
04/04/2023
Chasing Positive Bodies
We study the problem of chasing positive bodies in ℓ_1: given a sequence...
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
∙
02/10/2023
Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time
We show a fully dynamic algorithm for maintaining (1+ϵ)-approximate size...
research
∙
02/05/2023
Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction
The maximal k-edge-connected subgraphs problem is a classical graph clus...
research
∙
12/01/2022
Tight Conditional Lower Bounds for Vertex Connectivity Problems
We study the fine-grained complexity of graph connectivity problems in u...
research
∙
12/01/2022
Sublinear Algorithms for (1.5+ε)-Approximate Matching
We study sublinear time algorithms for estimating the size of maximum ma...
research
∙
10/25/2022
Deterministic Small Vertex Connectivity in Almost Linear Time
In the vertex connectivity problem, given an undirected n-vertex m-edge ...
research
∙
07/15/2022
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
In the dynamic linear program (LP) problem, we are given an LP undergoin...
research
∙
07/15/2022
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
We present dynamic algorithms with polylogarithmic update time for estim...
research
∙
07/11/2022
Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary
Designing dynamic algorithms against an adaptive adversary whose perform...
research
∙
07/08/2022
Vertex Sparsifiers for Hyperedge Connectivity
Recently, Chalermsook et al. [SODA'21(arXiv:2007.07862)] introduces a no...
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
∙
05/08/2022
Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
We revisit the vertex-failure connectivity oracle problem. This is one o...
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/02/2022
Optimal Vertex Connectivity Oracles
A k-vertex connectivity oracle for undirected G is a data structure that...
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
∙
11/09/2021
Gomory-Hu Tree in Subcubic Time
In 1961, Gomory and Hu showed that the max-flow values of all n 2 pairs ...
research
∙
11/07/2021
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
A dynamic algorithm against an adaptive adversary is required to be corr...
research
∙
11/02/2021
Fast Algorithms for Hop-Constrained Flows and Moving Cuts
Hop-constrained flows and their duals, moving cuts, are two fundamental ...
research
∙
06/04/2021
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
We give an n^2+o(1)-time algorithm for finding s-t min-cuts for all pair...
research
∙
06/03/2021
Deterministic Weighted Expander Decomposition in Almost-linear Time
In this note, we study the expander decomposition problem in a more gene...
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
∙
01/18/2021
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time
In the decremental single-source shortest paths problem, the goal is to ...
research
∙
01/14/2021
Minimum Cost Flows, MDPs, and ℓ_1-Regression in Nearly Linear Time for Dense Instances
In this paper we provide new randomized algorithms with improved runtime...
research
∙
09/17/2020
Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition
In the decremental single-source shortest paths (SSSP) problem, the inpu...
research
∙
09/05/2020
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Let G = (V,E,w) be a weighted, digraph subject to a sequence of adversar...
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
∙
08/19/2020
A Simple Deterministic Algorithm for Edge Connectivity
We show a deterministic algorithm for computing edge connectivity of a s...
research
∙
07/29/2020
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
There is a recent exciting line of work in distributed graph algorithms ...
research
∙
05/05/2020
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
We introduce a notion for hierarchical graph clustering which we call th...
research
∙
05/05/2020
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
We present a general framework of designing efficient dynamic approximat...
research
∙
04/17/2020
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Designing dynamic graph algorithms against an adaptive adversary is a ma...
research
∙
01/02/2020
Coarse-Grained Complexity for Dynamic Algorithms
To date, the only way to argue polynomial lower bounds for dynamic algor...
research
∙
12/05/2019
Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
The famous dynamic optimality conjecture of Sleator and Tarjan from 1985...
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
∙
07/18/2019
Sensitive Distance and Reachability Oracles for Large Batch Updates
In the sensitive distance oracle problem, there are three phases. We fir...
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/17/2019
Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
An (ϵ,ϕ)-expander decomposition of a graph G=(V,E) is a clustering of th...
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
∙
12/21/2018
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
We study the problem of graph clustering where the goal is to partition ...
research
∙
09/05/2018
Multi-finger binary search trees
We study multi-finger binary search trees (BSTs), a far-reaching extensi...
research
∙
02/15/2018