TY - CONF
AB - We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).
AU - Korhonen, Janne
AU - Paz, Ami
AU - Rybicki, Joel
AU - Schmid, Stefan
AU - Suomela, Jukka
ID - 10219
SN - 1868-8969
T2 - 35th International Symposium on Distributed Computing
TI - Brief announcement: Sinkless orientation is hard also in the supported LOCAL model
VL - 209
ER -
TY - JOUR
AB - We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include:
A (2+ϵ)-approximation for all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.
A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√) sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.
Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O~(n1/6) rounds.
AU - Censor-Hillel, Keren
AU - Dory, Michal
AU - Korhonen, Janne
AU - Leitersdorf, Dean
ID - 7939
JF - Distributed Computing
SN - 01782770
TI - Fast approximate shortest paths in the congested clique
ER -
TY - CONF
AB - The ability to leverage large-scale hardware parallelism has been one of the key enablers of the accelerated recent progress in machine learning. Consequently, there has been considerable effort invested into developing efficient parallel variants of classic machine learning algorithms. However, despite the wealth of knowledge on parallelization, some classic machine learning algorithms often prove hard to parallelize efficiently while maintaining convergence. In this paper, we focus on efficient parallel algorithms for the key machine learning task of inference on graphical models, in particular on the fundamental belief propagation algorithm. We address the challenge of efficiently parallelizing this classic paradigm by showing how to leverage scalable relaxed schedulers in this context. We present an extensive empirical study, showing that our approach outperforms previous parallel belief propagation implementations both in terms of scalability and in terms of wall-clock convergence time, on a range of practical applications.
AU - Aksenov, Vitaly
AU - Alistarh, Dan-Adrian
AU - Korhonen, Janne
ID - 9631
SN - 10495258
T2 - Advances in Neural Information Processing Systems
TI - Scalable belief propagation via relaxed scheduling
VL - 33
ER -
TY - CONF
AB - We design fast deterministic algorithms for distance computation in the CONGESTED CLIQUE model. Our key contributions include:
- A (2+ε)-approximation for all-pairs shortest paths problem in O(log²n / ε) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.
- A (1+ε)-approximation for multi-source shortest paths problem from O(√n) sources in O(log² n / ε) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.
Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in Õ(n^{1/6}) rounds.
AU - Censor-Hillel, Keren
AU - Dory, Michal
AU - Korhonen, Janne
AU - Leitersdorf, Dean
ID - 6933
SN - 9781450362177
T2 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin
TI - Fast approximate shortest paths in the congested clique
ER -
TY - CONF
AB - This paper investigates the power of preprocessing in the CONGEST model. Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to study the application of distributed algorithms in Software-Defined Networks (SDNs). In this paper, we show that a large class of lower bounds in the CONGEST model still hold in the SUPPORTED model, highlighting the robustness of these bounds. This also raises the question how much does
preprocessing help in the CONGEST model.
AU - Foerster, Klaus-Tycho
AU - Korhonen, Janne
AU - Rybicki, Joel
AU - Schmid, Stefan
ID - 6935
SN - 9781450362177
T2 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
TI - Does preprocessing help under congestion?
ER -
TY - JOUR
AB - In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an O(n1−2/ω) round matrix multiplication algorithm, where ω<2.3728639 is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include:
1. triangle and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) algorithm of Dolev et al. [DISC 2012],
2. a (1+o(1))-approximation of all-pairs shortest paths in O(n0.158) rounds, improving upon the O~(n1/2)-round (2+o(1))-approximation algorithm given by Nanongkai [STOC 2014], and
3. computing the girth in O(n0.158) rounds, which is the first non-trivial solution in this model.
In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.
AU - Censor-Hillel, Keren
AU - Kaski, Petteri
AU - Korhonen, Janne
AU - Lenzen, Christoph
AU - Paz, Ami
AU - Suomela, Jukka
ID - 7150
IS - 6
JF - Distributed Computing
SN - 0178-2770
TI - Algebraic methods in the congested clique
VL - 32
ER -