23 citations · 50 across the 10 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
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…
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…
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,…