215 citations · 689 across the 60 of their papers we have counts for
7 papers · 1 filter
Faster connectivity in low-rank hypergraphs via expander decomposition
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay +1
We design an algorithm for computing connectivity in hypergraphs which runs in time (the hides th…
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai +5
We present an -time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, a…
Distributed Weighted Min-Cut in Nearly-Optimal Time
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay +1
Minimum-weight cut (min-cut) is a basic measure of a network's connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], ther…
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg +4
Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees,…
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai +1
In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal approximation factor. (Throughout,…
Equivalence Classes and Conditional Hardness in Massively Parallel Computations
Danupon Nanongkai, Michele Scquizzato
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attent…