7 papers
Fully Dynamic Edge Connectivity in Time
Yotam Kenneth-Mordoch, Robert Krauthgamer
In the (fully) dynamic edge connectivity problem, the goal is to maintain the edge connectivity of an -vertex graph that undergoes edge insertions and deletions. Our m…
Faster Pseudo-Deterministic Minimum Cut
Yotam Kenneth-Mordoch
Pseudo-deterministic algorithms are randomized algorithms that, with high constant probability, output a fixed canonical solution. The study of pseudo-deterministic algorithms for…
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
Yotam Kenneth-Mordoch, Robert Krauthgamer
All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to find a minimum -cut for every pair of vertices . A recent line of work on fast algorithms for APM…
All-Pairs Minimum Cut using Cut Queries
Yotam Kenneth-Mordoch, Robert Krauthgamer
We present the first non-trivial algorithm for the all-pairs minimum cut problem in the cut-query model. Given cut-query access to an unweighted graph with vertices,…
Simple Algorithms for Fully Dynamic Edge Connectivity
Yotam Kenneth-Mordoch, Robert Krauthgamer
In the fully dynamic edge connectivity problem, the input is a simple graph undergoing edge insertions and deletions, and the goal is to maintain its edge connectivity, denoted…
On the Adversarial Robustness of Online Importance Sampling
Yotam Kenneth-Mordoch, Shay Sapir
This paper studies the adversarial-robustness of importance-sampling (aka sensitivity sampling); a useful algorithmic technique that samples elements with probabilities proportiona…