research
∙
02/22/2023
Finding a Small Vertex Cut on Distributed Networks
We present an algorithm for distributed networks to efficiently find a s...
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
∙
08/04/2022
Nearly Optimal Communication and Query Complexity of Bipartite Matching
We settle the complexities of the maximum-cardinality bipartite matching...
research
∙
01/14/2022
Cut query algorithms with star contraction
We study the complexity of determining the edge connectivity of a simple...
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
∙
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
∙
11/05/2019
