Zobrazeno 1 - 10
of 72
pro vyhledávání: '"Keren Censor-Hillel"'
Publikováno v:
ACM Transactions on Algorithms. 17:1-40
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 contribution of bit-gadgets is twofold. First, developing careful sparse
Autor:
Yehuda Afek, Keren Censor-Hillel, Pierre Fraigniaud, Seth Gilbert, Gopal Pandurangan, Gadi Taubenfeld
Publikováno v:
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing.
Publikováno v:
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
PODC
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing-PODC 19
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing-PODC '19
PODC
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing-PODC 19
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing-PODC '19
We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include: A $$(2+\epsilon )$$ ( 2 + ϵ ) -approximation for all-pairs shortest paths in $$O(\log ^2{n} / \epsilon )$$ O ( log 2 n /
Publikováno v:
Theoretical Computer Science. 811:112-124
We study a new model of verification of boolean predicates over distributed networks. Given a network configuration, the proof-labeling scheme (PLS) model defines a distributed proof in the form of a label that is given to each node, and all nodes lo
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:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8184bda8aecc97b8f5a03fabf7f64b77
Publikováno v:
SPAA
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:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8e85c45726d942e0208bc06b11a27940
http://arxiv.org/abs/2105.06068
http://arxiv.org/abs/2105.06068
Publikováno v:
Structural Information and Communication Complexity ISBN: 9783030795269
SIROCCO
SIROCCO
This paper provides three nearly-optimal algorithms for scheduling t jobs in the \(\mathsf {CLIQUE}\) model. First, we present a deterministic scheduling algorithm that runs in \(O(\mathsf {Global}\mathsf {Congestion} + \mathsf {dilation})\) rounds f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0d8b36ae34735805ff57e6c0cb03ca88
https://doi.org/10.1007/978-3-030-79527-6_4
https://doi.org/10.1007/978-3-030-79527-6_4
Publikováno v:
SPAA
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 / deleted per round. We show that the problems of $k$-clique membership l
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7cba12a06427ecb614158bd4d6403a81
http://arxiv.org/abs/2009.08208
http://arxiv.org/abs/2009.08208
Publikováno v:
Proceedings of the 39th Symposium on Principles of Distributed Computing
PODC
PODC
We show an $\tilde{O}(n^{p/(p+2)})$-round algorithm in the \congest model for \emph{listing} of $K_p$ (a clique with $p$ nodes), for all $p =4, p\geq 6$. For $p = 5$, we show an $\tilde{O}(n^{3/4})$-round algorithm. For $p=4$ and $p=5$, our results i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ddc52690bb400d0f755ecf9c63759a63
http://arxiv.org/abs/2007.05316
http://arxiv.org/abs/2007.05316