1 Search Results for "Fiat, Nimrod"


Document
Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles

Authors: Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


Abstract
In this paper we give sublinear-time distributed algorithms in the CONGEST model for subgraph detection for two classes of graphs: cliques and even-length cycles. We show for the first time that all copies of 4-cliques and 5-cliques in the network graph can be listed in sublinear time, O(n^{5/6+o(1)}) rounds and O(n^{21/22+o(1)}) rounds, respectively. Prior to our work, it was not known whether it was possible to even check if the network contains a 4-clique or a 5-clique in sublinear time. For even-length cycles, C_{2k}, we give an improved sublinear-time algorithm, which exploits a new connection to extremal combinatorics. For example, for 6-cycles we improve the running time from O~(n^{5/6}) to O~(n^{3/4}) rounds. We also show two obstacles on proving lower bounds for C_{2k}-freeness: First, we use the new connection to extremal combinatorics to show that the current lower bound of Omega~(sqrt{n}) rounds for 6-cycle freeness cannot be improved using partition-based reductions from 2-party communication complexity, the technique by which all known lower bounds on subgraph detection have been proven to date. Second, we show that there is some fixed constant delta in (0,1/2) such that for any k, a Omega(n^{1/2+delta}) lower bound on C_{2k}-freeness implies new lower bounds in circuit complexity. For general subgraphs, it was shown in [Orr Fischer et al., 2018] that for any fixed k, there exists a subgraph H of size k such that H-freeness requires Omega~(n^{2-Theta(1/k)}) rounds. It was left as an open problem whether this is tight, or whether some constant-sized subgraph requires truly quadratic time to detect. We show that in fact, for any subgraph H of constant size k, the H-freeness problem can be solved in O(n^{2 - Theta(1/k)}) rounds, nearly matching the lower bound of [Orr Fischer et al., 2018].

Cite as

Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.DISC.2019.15,
  author =	{Eden, Talya and Fiat, Nimrod and Fischer, Orr and Kuhn, Fabian and Oshman, Rotem},
  title =	{{Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.15},
  URN =		{urn:nbn:de:0030-drops-113224},
  doi =		{10.4230/LIPIcs.DISC.2019.15},
  annote =	{Keywords: Distributed Computing, Subgraph Freeness, CONGEST}
}
  • Refine by Author
  • 1 Eden, Talya
  • 1 Fiat, Nimrod
  • 1 Fischer, Orr
  • 1 Kuhn, Fabian
  • 1 Oshman, Rotem

  • Refine by Classification
  • 1 Networks → Network algorithms
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Lower bounds and information complexity

  • Refine by Keyword
  • 1 CONGEST
  • 1 Distributed Computing
  • 1 Subgraph Freeness

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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