13 citations · 23 across the 12 of their papers we have counts for
21 papers
Bounded Memory in Distributed Networks
Ran Ben Basat, Keren Censor-Hillel, Yi-Jun Chang +3
The recent advent of programmable switches makes distributed algorithms readily deployable in real-world datacenter networks. However, there are still gaps between theory and pract…
Mini-batch -means terminates within iterations
Gregory Schwartzman
We answer the question: "Does local progress (on batches) imply global progress (on the entire dataset) for mini-batch -means?". Specifically, we consider mini-batch -means w…
Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs
Taisuke Izumi, Naoki Kitamura, Takamasa Naruse +1
We consider global problems, i.e. problems that take at least diameter time, even when the bandwidth is not restricted. We show that all problems considered admit efficient solutio…
FRANCIS: Fast Reaction Algorithms for Network Coordination In Switches
Wenchen Han, Vic Feng, Gregory Schwartzman +4
Optimizing the reaction to network events, which is critical in tasks such as clock synchronization, multicast, and routing, becomes increasingly challenging as networks grow large…
SGD Through the Lens of Kolmogorov Complexity
Gregory Schwartzman
We prove that stochastic gradient descent (SGD) finds a solution that achieves classification accuracy on the entire dataset. We do so under two main assumptions: (1. Local…
On the Complexity of Load Balancing in Dynamic Networks
Seth Gilbert, Uri Meir, Ami Paz +1
In the load balancing problem, each node in a network is assigned a load, and the goal is to equally distribute the loads among the nodes, by preforming local load exchanges. While…
Smoothed Analysis of Population Protocols
Gregory Schwartzman, Yuichi Sudo
In this work, we initiate the study of \emph{smoothed analysis} of population protocols. We consider a population protocol model where an adaptive adversary dictates the interactio…
Models of Smoothing in Dynamic Networks
Uri Meir, Ami Paz, Gregory Schwartzman
Smoothed analysis is a framework suggested for mediating gaps between worst-case and average-case complexities. In a recent work, Dinitz et al.~[Distributed Computing, 2018] sugges…
Finding Subgraphs in Highly Dynamic Networks
Keren Censor-Hillel, Victor I. Kolobov, Gregory Schwartzman
In this paper we consider the fundamental problem of finding subgraphs in highly dynamic distributed networks - networks which allow an arbitrary number of links to be inserted / d…
Improved Distributed Approximations for Maximum Independent Set
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild +1
We present improved results for approximating maximum-weight independent set ($\MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let and…
Optimal Distributed Covering Algorithms
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi +1
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank . This problem is equivalent to the Minimum…
Fast Deterministic Algorithms for Highly-Dynamic Networks
Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov +2
This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which *arbitrarily many* edge changes may occur in each roun…
Optimal Distributed Weighted Set Cover Approximation
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi +1
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank . This problem is equivalent to the Minimum…
Parameterized Distributed Algorithms
Ran Ben-Basat, Ken-ichi Kawarabayashi, Gregory Schwartzman
In this work, we initiate a thorough study of parameterized graph optimization problems in the distributed setting. In a parameterized problem, an algorithm decides whether a solut…
A Deterministic Distributed -Approximation for Weighted Vertex Cover in Rounds
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi +1
We present a deterministic distributed -approximation algorithm for the Minimum Weight Vertex Cover problem in the CONGEST model whose round complexity is $O(\log n \log Δ/ \log…
Adapting Local Sequential Algorithms to the Distributed Setting
Ken-ichi Kawarabayashi, Gregory Schwartzman
It is a well known fact that sequential algorithms which exhibit a strong "local" nature can be adapted to the distributed setting given a legal graph coloring. The running time of…
Distributed Approximation of Maximum Independent Set and Maximum Matching
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari +1
We present a simple distributed -approximation algorithm for maximum weight independent set (MaxIS) in the model which completes in $O(\texttt{MIS}(G)\cdot \l…
A -Approximation for Maximum Weight Matching in the Semi-Streaming Model
Ami Paz, Gregory Schwartzman
We present a simple deterministic single-pass -approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently…
Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
Keren Censor-Hillel, Merav Parter, Gregory Schwartzman
This paper addresses the cornerstone family of \emph{local problems} in distributed computing, and investigates the curious gap between randomized and deterministic solutions under…
A Distributed -Approximation for Vertex Cover in Rounds
Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman
We present a simple deterministic distributed -approximation algorithm for minimum weight vertex cover, which completes in rounds, where is the max…
Fast Distributed Algorithms for Testing Graph Properties
Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman +1
We initiate a thorough study of \emph{distributed property testing} -- producing algorithms for the approximation problems of property testing in the CONGEST model. In particular,…