Zobrazeno 1 - 10
of 27
pro vyhledávání: '"Leitersdorf, Dean"'
In this paper, we present new algorithms for approximating All-Pairs Shortest Paths (APSP) in the Congested Clique model. We present randomized algorithms for weighted undirected graphs. Our first contribution is an $O(1)$-approximate APSP algorithm
Externí odkaz:
http://arxiv.org/abs/2405.02695
We revisit the classic broadcast problem, wherein we have $k$ messages, each composed of $O(\log{n})$ bits, distributed arbitrarily across a network. The objective is to broadcast these messages to all nodes in the network. In the distributed CONGEST
Externí odkaz:
http://arxiv.org/abs/2404.12930
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 access to two different communication modes: high-bandwidth local communic
Externí odkaz:
http://arxiv.org/abs/2311.09548
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 do better. However, most inputs of interest can be solved much more eff
Externí odkaz:
http://arxiv.org/abs/2304.06317
Autor:
Leitersdorf, Orian, Leitersdorf, Dean, Gal, Jonathan, Dahan, Mor, Ronen, Ronny, Kvatinsky, Shahar
Digital processing-in-memory (PIM) architectures are rapidly emerging to overcome the memory-wall bottleneck by integrating logic within memory elements. Such architectures provide vast computational power within the memory itself in the form of para
Externí odkaz:
http://arxiv.org/abs/2206.04218
Publikováno v:
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. July 2022. Pp. 271-280
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 breakthroughs. A crucial aspect that remained open was whether deterministic alg
Externí odkaz:
http://arxiv.org/abs/2205.09245
The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed algorithms that run faster than the fastest known classical counterpart
Externí odkaz:
http://arxiv.org/abs/2201.03000
We extract a core principle underlying seemingly different fundamental distributed settings, showing sparsity awareness may induce faster algorithms for problems in these settings. To leverage this, we establish a new framework by developing an inter
Externí odkaz:
http://arxiv.org/abs/2105.06068
Autor:
Censor-Hillel, Keren, Fischer, Orr, Gonen, Tzlil, Gall, François Le, Leitersdorf, Dean, Oshman, Rotem
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 state of the art by polynomial factors, and for girth, we obtain an const
Externí odkaz:
http://arxiv.org/abs/2101.07590
Publikováno v:
Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), 2878-2891, 2021
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 tight bounds are known in this area. For triangle (i.e., 3-clique) li
Externí odkaz:
http://arxiv.org/abs/2011.07405