92 citations · 170 across the 35 of their papers we have counts for
33 papers · 1 filter
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…
When MIS and Maximal Matching are Easy in the Congested Clique
Keren Censor-Hillel, Tomer Even, Maxime Flin +1
Two of the most fundamental distributed symmetry-breaking problems are that of finding a maximal independent set (MIS) and a maximal matching (MM) in a graph. It is a major open qu…
On Distributed Computation of the Minimum Triangle Edge Transversal
Keren Censor-Hillel, Majd Khoury
The distance of a graph from being triangle-free is a fundamental graph parameter, counting the number of edges that need to be removed from a graph in order for it to become trian…
Near-Optimal Fault Tolerance for Efficient Batch Matrix Multiplication via an Additive Combinatorics Lens
Keren Censor-Hillel, Yuka Machino, Pedro Soto
Fault tolerance is a major concern in distributed computational settings. In the classic master-worker setting, a server (the master) needs to perform some heavy computation which…
Distributed Computations in Fully-Defective Networks
Keren Censor-Hillel, Shir Cohen, Ran Gelles +1
We address fully-defective asynchronous networks, in which all links are subject to an unlimited number of alteration errors, implying that all messages in the network may be compl…
Deterministic Near-Optimal Distributed Listing of Cliques
Keren Censor-Hillel, Dean Leitersdorf, David Vulakh
The importance of classifying connections in large graphs has been the motivation for a rich line of work on distributed subgraph finding that has led to exciting recent breakthrou…
On Sparsity Awareness in Distributed Computations
Keren Censor-Hillel, Dean Leitersdorf, Volodymyr Polosukhin
We extract a core principle underlying seemingly different fundamental distributed settings, showing sparsity awareness may induce faster algorithms for problems in these settings.…
Near-Optimal Scheduling in the Congested Clique
Keren Censor-Hillel, Yannic Maus, Volodymyr Polosukhin
This paper provides three nearly-optimal algorithms for scheduling jobs in the model. First, we present a deterministic scheduling algorithm that runs in $O(\…
Distributed Distance Approximation
Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard +2
Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can…
Tight Distributed Listing of Cliques
Keren Censor-Hillel, Yi-Jun Chang, François Le Gall +1
Much progress has recently been made in understanding the complexity landscape of subgraph finding problems in the CONGEST model of distributed computing. However, so far, very few…
Distance Computations in the Hybrid Network Model via Oracle Simulations
Keren Censor-Hillel, Dean Leitersdorf, Volodymyr Polosukhin
The Hybrid network model was introduced in [Augustine et al., SODA '20] for laying down a theoretical foundation for networks which combine two possible modes of communication: One…
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…
On Distributed Listing of Cliques
Keren Censor-Hillel, François Le Gall, Dean Leitersdorf
We show an -round algorithm in the \congest model for \emph{listing} of (a clique with nodes), for all . For , we show an $\…
Distributed Detection of Cliques in Dynamic Networks
Matthias Bonne, Keren Censor-Hillel
This paper provides an in-depth study of the fundamental problems of finding small subgraphs in distributed dynamic networks. While some problems are trivially easy to handle, such…
Fast Approximate Shortest Paths in the Congested Clique
Keren Censor-Hillel, Michal Dory, Janne H. Korhonen +1
We design fast deterministic algorithms for distance computation in the congested clique model. Our key contributions include: -- A -approximation for all-pairs shortest pat…
Smaller Cuts, Higher Lower Bounds
Amir Abboud, Keren Censor-Hillel, Seri Khoury +1
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The con…
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…
The Sparsest Additive Spanner via Multiple Weighted BFS Trees
Keren Censor-Hillel, Ami Paz, Noam Ravid
Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pa…
Distributed Reconfiguration of Maximal Independent Sets
Keren Censor-Hillel, Mikaël Rabie
In this paper, we investigate a distributed maximal independent set (MIS) reconfiguration problem, in which there are two maximal independent sets for which every node is given its…
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…
Broadcasting in Noisy Radio Networks
Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz +1
The widely-studied radio network model [Chlamtac and Kutten, 1985] is a graph-based description that captures the inherent impact of collisions in wireless communication. In this m…
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
Keren Censor-Hillel, Seri Khoury, Ami Paz
We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact comput…
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…
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
Amir Abboud, Keren Censor-Hillel, Seri Khoury
We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Speci…