23 citations · 50 across the 10 of their papers we have counts for
16 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…
Improved All-Pairs Approximate Shortest Paths in Congested Clique
Hong Duc Bui, Shashwat Chandra, Yi-Jun Chang +2
In this paper, we present a new randomized -approximation algorithm for the All-Pairs Shortest Paths (APSP) problem in weighted undirected graphs that runs in just $O(\log \l…
Fast Broadcast in Highly Connected Networks
Shashwat Chandra, Yi-Jun Chang, Michal Dory +2
We revisit the classic broadcast problem, wherein we have messages, each composed of bits, distributed arbitrarily across a network. The objective is to broadcast…
Universally Optimal Information Dissemination and Shortest Paths in the HYBRID Distributed Model
Yi-Jun Chang, Oren Hecht, Dean Leitersdorf +1
In this work we consider the HYBRID model of distributed computing, introduced recently by Augustine, Hinnenthal, Kuhn, Scheideler, and Schneider (SODA 2020), where nodes have acce…
Universally Optimal Deterministic Broadcasting in the HYBRID Distributed Model
Yi-Jun Chang, Oren Hecht, Dean Leitersdorf
In theoretical computer science, it is a common practice to show existential lower bounds for problems, meaning there is a family of pathological inputs on which no algorithm can d…
AritPIM: High-Throughput In-Memory Arithmetic
Orian Leitersdorf, Dean Leitersdorf, Jonathan Gal +3
Digital processing-in-memory (PIM) architectures are rapidly emerging to overcome the memory-wall bottleneck by integrating logic within memory elements. Such architectures provide…
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…
Quantum Distributed Algorithms for Detection of Cliques
Keren Censor-Hillel, Orr Fischer, François Le Gall +2
The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed a…
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.…
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen +3
In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the sta…
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…
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 $\…
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…
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…
Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model
Keren Censor-Hillel, Dean Leitersdorf, Elia Turner
We multiply two matrices over semirings in the Congested Clique model, where fully connected nodes communicate synchronously using -bit messages,…