2 citations · 3 across the 3 of their papers we have counts for
4 papers · 1 filter
A Simple Algorithm for Dynamic Carpooling with Recourse
Yuval Efron, Shyamal Patel, Cliff Stein
We give an algorithm for the fully-dynamic carpooling problem with recourse: Edges arrive and depart online from a graph with nodes according to an adaptive adversary. Our…
Cut query algorithms with star contraction
Simon Apers, Yuval Efron, Paweł Gawrychowski +3
We study the complexity of determining the edge connectivity of a simple graph with cut queries. We show that (i) there is a bounded-error randomized algorithm that computes edge c…
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…
Hardness of Distributed Optimization
Nir Bachrach, Keren Censor-Hillel, Michal Dory +3
This paper studies lower bounds for fundamental optimization problems in the CONGEST model. We show that solving problems exactly in this model can be a hard task, by providing $\t…