6 Search Results for "Leitersdorf, Dean"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.35
Quantum Distributed Algorithms for Detection of Cliques

Authors: Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
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 counterparts, and even separations between the two models. A prime example is the result by Izumi, Le Gall, and Magniez [STACS 2020], who showed that triangle detection by quantum distributed algorithms is easier than triangle listing, while an analogous result is not known in the classical case. In this paper we present a framework for fast quantum distributed clique detection. This improves upon the state-of-the-art for the triangle case, and is also more general, applying to larger clique sizes. Our main technical contribution is a new approach for detecting cliques by encapsulating this as a search task for nodes that can be added to smaller cliques. To extract the best complexities out of our approach, we develop a framework for nested distributed quantum searches, which employ checking procedures that are quantum themselves. Moreover, we show a circuit-complexity barrier on proving a lower bound of the form Ω(n^{3/5+ε}) for K_p-detection for any p ≥ 4, even in the classical (non-quantum) distributed CONGEST setting.
Cite as

Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum Distributed Algorithms for Detection of Cliques. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 35:1-35:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ITCS.2022.35,
  author =	{Censor-Hillel, Keren and Fischer, Orr and Le Gall, Fran\c{c}ois and Leitersdorf, Dean and Oshman, Rotem},
  title =	{{Quantum Distributed Algorithms for Detection of Cliques}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{35:1--35:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.35},
  URN =		{urn:nbn:de:0030-drops-156319},
  doi =		{10.4230/LIPIcs.ITCS.2022.35},
  annote =	{Keywords: distributed graph algorithms, quantum algorithms, cycles, cliques, Congested Clique, CONGEST}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.58
Lower Bounds for Induced Cycle Detection in Distributed Computing

Authors: François Le Gall and Masayuki Miyamoto

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
The distributed subgraph detection asks, for a fixed graph H, whether the n-node input graph contains H as a subgraph or not. In the standard CONGEST model of distributed computing, the complexity of clique/cycle detection and listing has received a lot of attention recently. In this paper we consider the induced variant of subgraph detection, where the goal is to decide whether the n-node input graph contains H as an induced subgraph or not. We first show a Ω̃(n) lower bound for detecting the existence of an induced k-cycle for any k ≥ 4 in the CONGEST model. This lower bound is tight for k = 4, and shows that the induced variant of k-cycle detection is much harder than the non-induced version. This lower bound is proved via a reduction from two-party communication complexity. We complement this result by showing that for 5 ≤ k ≤ 7, this Ω̃(n) lower bound cannot be improved via the two-party communication framework. We then show how to prove stronger lower bounds for larger values of k. More precisely, we show that detecting an induced k-cycle for any k ≥ 8 requires Ω̃(n^{2-Θ{(1/k)}}) rounds in the CONGEST model, nearly matching the known upper bound Õ(n^{2-Θ{(1/k)}}) of the general k-node subgraph detection (which also applies to the induced version) by Eden, Fiat, Fischer, Kuhn, and Oshman [DISC 2019]. Finally, we investigate the case where H is the diamond (the diamond is obtained by adding an edge to a 4-cycle, or equivalently removing an edge from a 4-clique), and show non-trivial upper and lower bounds on the complexity of the induced version of diamond detecting and listing.
Cite as

François Le Gall and Masayuki Miyamoto. Lower Bounds for Induced Cycle Detection in Distributed Computing. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 58:1-58:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.ISAAC.2021.58,
  author =	{Le Gall, Fran\c{c}ois and Miyamoto, Masayuki},
  title =	{{Lower Bounds for Induced Cycle Detection in Distributed Computing}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{58:1--58:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.58},
  URN =		{urn:nbn:de:0030-drops-154919},
  doi =		{10.4230/LIPIcs.ISAAC.2021.58},
  annote =	{Keywords: Distributed computing, Lower bounds, Subgraph detection}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2021.3
Distributed Subgraph Finding: Progress and Challenges (Invited Talk)

Authors: Keren Censor-Hillel

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
This is a survey of the exciting recent progress made in understanding the complexity of distributed subgraph finding problems. It overviews the results and techniques for assorted variants of subgraph finding problems in various models of distributed computing, and states intriguing open questions.
Cite as

Keren Censor-Hillel. Distributed Subgraph Finding: Progress and Challenges (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{censorhillel:LIPIcs.ICALP.2021.3,
  author =	{Censor-Hillel, Keren},
  title =	{{Distributed Subgraph Finding: Progress and Challenges}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.3},
  URN =		{urn:nbn:de:0030-drops-140726},
  doi =		{10.4230/LIPIcs.ICALP.2021.3},
  annote =	{Keywords: distributed algorithms, subgraph finding, limited bandwidth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.21
Distance Computations in the Hybrid Network Model via Oracle Simulations

Authors: Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
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 mode allows high-bandwidth communication with neighboring nodes, and the other allows low-bandwidth communication over few long-range connections at a time. This fundamentally abstracts networks such as hybrid data centers, and class-based software-defined networks. Our technical contribution is a density-aware approach that allows us to simulate a set of oracles for an overlay skeleton graph over a Hybrid network. As applications of our oracle simulations, with additional machinery that we provide, we derive fast algorithms for fundamental distance-related tasks. One of our core contributions is an algorithm in the Hybrid model for computing exact weighted shortest paths from Õ(n^{1/3}) sources which completes in Õ(n^{1/3}) rounds w.h.p. This improves, in both the runtime and the number of sources, upon the algorithm of [Kuhn and Schneider, PODC ’20], which computes shortest paths from a single source in Õ(n^{2/5}) rounds w.h.p. We additionally show a 2-approximation for weighted diameter and a (1+ε)-approximation for unweighted diameter, both in Õ(n^{1/3}) rounds w.h.p., which is comparable to the ̃ Ω(n^{1/3}) lower bound of [Kuhn and Schneider, PODC ’20] for a (2-ε)-approximation for weighted diameter and an exact unweighted diameter. We also provide fast distance approximations from multiple sources and fast approximations for eccentricities.
Cite as

Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin. Distance Computations in the Hybrid Network Model via Oracle Simulations. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.STACS.2021.21,
  author =	{Censor-Hillel, Keren and Leitersdorf, Dean and Polosukhin, Volodymyr},
  title =	{{Distance Computations in the Hybrid Network Model via Oracle Simulations}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.21},
  URN =		{urn:nbn:de:0030-drops-136663},
  doi =		{10.4230/LIPIcs.STACS.2021.21},
  annote =	{Keywords: Distributed graph algorithms, Hybrid network model, Distance computations}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.33
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs

Authors: Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
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 a constant-time algorithm for additive +1 approximation in Congested Clique, and the first parametrized algorithm for exact computation in Congest. In the Congested Clique model, we first develop a technique for learning small neighborhoods, and apply it to obtain an O(1)-round algorithm that computes the girth with only an additive +1 error. Next, we introduce a new technique (the partition tree technique) allowing for efficiently listing all copies of any subgraph, which is deterministic and improves upon the state-of the-art for non-dense graphs. We give two concrete applications of the partition tree technique: First we show that for constant k, it is possible to solve C_{2k}-detection in O(1) rounds in the Congested Clique, improving on prior work, which used fast matrix multiplication and thus had polynomial round complexity. Second, we show that in triangle-free graphs, the girth can be exactly computed in time polynomially faster than the best known bounds for general graphs. We remark that no analogous result is currently known for sequential algorithms. In the Congest model, we describe a new approach for finding cycles, and instantiate it in two ways: first, we show a fast parametrized algorithm for girth with round complexity Õ(min{g⋅ n^{1-1/Θ(g)},n}) for any girth g; and second, we show how to find small even-length cycles C_{2k} for k = 3,4,5 in O(n^{1-1/k}) rounds. This is a polynomial improvement upon the previous running times; for example, our C₆-detection algorithm runs in O(n^{2/3}) rounds, compared to O(n^{3/4}) in prior work. Finally, using our improved C₆-freeness algorithm, and the barrier on proving lower bounds on triangle-freeness of Eden et al., we show that improving the current ̃Ω(√n) lower bound for C₆-freeness of Korhonen et al. by any polynomial factor would imply strong circuit complexity lower bounds.
Cite as

Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2020.33,
  author =	{Censor-Hillel, Keren and Fischer, Orr and Gonen, Tzlil and Le Gall, Fran\c{c}ois and Leitersdorf, Dean and Oshman, Rotem},
  title =	{{Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.33},
  URN =		{urn:nbn:de:0030-drops-131115},
  doi =		{10.4230/LIPIcs.DISC.2020.33},
  annote =	{Keywords: distributed graph algorithms, cycles, girth, Congested Clique, CONGEST}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.4
Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model

Authors: Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
We show how to multiply two n x n matrices S and T over semirings in the Congested Clique model, where n nodes communicate in a fully connected synchronous network using O(log{n})-bit messages, within O(nz(S)^{1/3} nz(T)^{1/3}/n + 1) rounds of communication, where nz(S) and nz(T) denote the number of non-zero elements in S and T, respectively. By leveraging the sparsity of the input matrices, our algorithm greatly reduces communication costs compared with general multiplication algorithms [Censor-Hillel et al., PODC 2015], and thus improves upon the state-of-the-art for matrices with o(n^2) non-zero elements. Moreover, our algorithm exhibits the additional strength of surpassing previous solutions also in the case where only one of the two matrices is such. Particularly, this allows to efficiently raise a sparse matrix to a power greater than 2. As applications, we show how to speed up the computation on non-dense graphs of 4-cycle counting and all-pairs-shortest-paths. Our algorithmic contribution is a new deterministic method of restructuring the input matrices in a sparsity-aware manner, which assigns each node with element-wise multiplication tasks that are not necessarily consecutive but guarantee a balanced element distribution, providing for communication-efficient multiplication. Moreover, this new deterministic method for restructuring matrices may be used to restructure the adjacency matrix of input graphs, enabling faster deterministic solutions for graph related problems. As an example, we present a new sparsity aware, deterministic algorithm which solves the triangle listing problem in O(m/n^{5/3} + 1) rounds, a complexity that was previously obtained by a randomized algorithm [Pandurangan et al., SPAA 2018], and that matches the known lower bound of Omega~(n^{1/3}) when m=n^2 of [Izumi and Le Gall, PODC 2017, Pandurangan et al., SPAA 2018]. Naturally, our triangle listing algorithm also implies triangle counting within the same complexity of O(m/n^{5/3} + 1) rounds, which is (possibly more than) a cubic improvement over the previously known deterministic O(m^2/n^3)-round algorithm [Dolev et al., DISC 2012].
Cite as

Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2018.4,
  author =	{Censor-Hillel, Keren and Leitersdorf, Dean and Turner, Elia},
  title =	{{Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.4},
  URN =		{urn:nbn:de:0030-drops-100645},
  doi =		{10.4230/LIPIcs.OPODIS.2018.4},
  annote =	{Keywords: congested clique, matrix multiplication, triangle listing}
}
  • Refine by Author
  • 5 Censor-Hillel, Keren
  • 4 Leitersdorf, Dean
  • 3 Le Gall, François
  • 2 Fischer, Orr
  • 2 Oshman, Rotem
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Distributed algorithms
  • 3 Networks → Network algorithms
  • 1 Theory of computation → Distributed computing models
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Lower bounds and information complexity

  • Refine by Keyword
  • 2 CONGEST
  • 2 Congested Clique
  • 2 cycles
  • 2 distributed graph algorithms
  • 1 Distance computations
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2021
  • 1 2019
  • 1 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact