6 Search Results for "Khoury, Seri"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.25
Listing 4-Cycles

Authors: Amir Abboud, Seri Khoury, Oree Leibowitz, and Ron Safier

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
We study the fine-grained complexity of listing all 4-cycles in a graph on n nodes, m edges, and t such 4-cycles. The main result is an Õ(min(n²,m^{4/3})+t) upper bound, which is best-possible up to log factors unless the long-standing O(min(n²,m^{4/3})) upper bound for detecting a 4-cycle can be broken. Moreover, it almost-matches recent 3-SUM-based lower bounds for the problem by Abboud, Bringmann, and Fischer (STOC 2023) and independently by Jin and Xu (STOC 2023). Notably, our result separates 4-cycle listing from the closely related triangle listing for which higher conditional lower bounds exist, and rule out such a "detection plus t" bound. We also show by simple arguments that our bound cannot be extended to mild generalizations of the problem such as reporting all pairs of nodes that participate in a 4-cycle. [Independent work: Jin and Xu [Ce Jin and Yinzhan Xu, 2023] also present an algorithm with the same time bound.]
Cite as

Amir Abboud, Seri Khoury, Oree Leibowitz, and Ron Safier. Listing 4-Cycles. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.FSTTCS.2023.25,
  author =	{Abboud, Amir and Khoury, Seri and Leibowitz, Oree and Safier, Ron},
  title =	{{Listing 4-Cycles}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.25},
  URN =		{urn:nbn:de:0030-drops-193985},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.25},
  annote =	{Keywords: Graph algorithms, cycles listing, subgraph detection, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.19
Improved Hardness of Approximation of Diameter in the CONGEST Model

Authors: Ofer Grossman, Seri Khoury, and Ami Paz

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

Abstract
We study the problem of approximating the diameter D of an unweighted and undirected n-node graph in the congest model. Through a connection to extremal combinatorics, we show that a (6/11 + ε)-approximation requires Ω(n^{1/6}/log n) rounds, a (4/7 + ε)-approximation requires Ω(n^{1/4}/log n) rounds, and a (3/5 + ε)-approximation requires Ω(n^{1/3}/log n) rounds. These lower bounds are robust in the sense that they hold even against algorithms that are allowed to return an additional small additive error. Prior to our work, only lower bounds for (2/3 + ε)-approximation were known [Frischknecht et al. SODA 2012, Abboud et al. DISC 2016]. Furthermore, we prove that distinguishing graphs of diameter 3 from graphs of diameter 5 requires Ω(n/log n) rounds. This stands in sharp contrast to previous work: while there is an algorithm that returns an estimate ⌊ 2/3D ⌋ ≤ D̃ ≤ D in Õ(√n+D) rounds [Holzer et al. DISC 2014], our lower bound implies that any algorithm for returning an estimate 2/3D ≤ D̃ ≤ D requires ̃Ω(n) rounds.
Cite as

Ofer Grossman, Seri Khoury, and Ami Paz. Improved Hardness of Approximation of Diameter in the CONGEST Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{grossman_et_al:LIPIcs.DISC.2020.19,
  author =	{Grossman, Ofer and Khoury, Seri and Paz, Ami},
  title =	{{Improved Hardness of Approximation of Diameter in the CONGEST Model}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{19:1--19:16},
  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.19},
  URN =		{urn:nbn:de:0030-drops-130972},
  doi =		{10.4230/LIPIcs.DISC.2020.19},
  annote =	{Keywords: Distributed graph algorithms, Approximation algorithms, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.35
Improved Distributed Approximations for Maximum Independent Set

Authors: Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman

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

Abstract
We present improved results for approximating maximum-weight independent set (MaxIS) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let n and Δ be the number of nodes and maximum degree, respectively, and let MIS(n,Δ) be the running time of finding a maximal independent set (MIS) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δ-approximation for MaxIS in O(MIS(n,Δ)log W) rounds, where W is the maximum weight of a node in the graph, which can be as large as poly (n). Whether their algorithm is deterministic or randomized that succeeds with high probability depends on the MIS algorithm that is used as a black-box. Our results: 1) A deterministic O(MIS(n,Δ)/ε)-round algorithm that finds a (1+ε)Δ-approximation for MaxIS in the CONGEST model. 2) A randomized (poly(log log n)/ε)-round algorithm that finds, with high probability, a (1+ε)Δ-approximation for MaxIS in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an exponential speed-up in the running time over the previous best known result. 3) A randomized O(log n⋅ poly(log log n)/ε)-round algorithm that finds, with high probability, a 8(1+ε)α-approximation for MaxIS in the CONGEST model, where α is the arboricity of the graph. For graphs of arboricity α < Δ/(8(1+ε)), this result improves upon the previous best known result in both the approximation factor and the running time. One may wonder whether it is possible to approximate MaxIS with high probability in fewer than poly(log log n) rounds. Interestingly, a folklore randomized ranking algorithm by Boppana implies a single round algorithm that gives an expected Δ-approximation in the CONGEST model. However, it is unclear how to convert this algorithm to one that succeeds with high probability without sacrificing a large number of rounds. For unweighted graphs of maximum degree Δ ≤ n/log n, we show a new analysis of the randomized ranking algorithm, which we combine with the local-ratio technique, to provide a O(1/ε)-round algorithm in the CONGEST model that, with high probability, finds an independent set of size at least n/((1+ε)(Δ+1)). This result cannot be extended to very high degree graphs, as we show a lower bound of Ω(log^*n) rounds for any randomized algorithm that with probability at least 1-1/log n finds an independent set of size Ω(n/Δ). This lower bound holds even for the LOCAL model. The hard instances that we use to prove our lower bound are graphs of maximum degree Δ = Ω(n/log^*n).
Cite as

Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman. Improved Distributed Approximations for Maximum Independent Set. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kawarabayashi_et_al:LIPIcs.DISC.2020.35,
  author =	{Kawarabayashi, Ken-ichi and Khoury, Seri and Schild, Aaron and Schwartzman, Gregory},
  title =	{{Improved Distributed Approximations for Maximum Independent Set}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{35:1--35:16},
  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.35},
  URN =		{urn:nbn:de:0030-drops-131135},
  doi =		{10.4230/LIPIcs.DISC.2020.35},
  annote =	{Keywords: Distributed graph algorithms, Approximation algorithms, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.6
Parameterized Distributed Algorithms

Authors: Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman

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

Abstract
In this work, we initiate a thorough study of graph optimization problems parameterized by the output size in the distributed setting. In such a problem, an algorithm decides whether a solution of size bounded by k exists and if so, it finds one. We study fundamental problems, including Minimum Vertex Cover (MVC), Maximum Independent Set (MaxIS), Maximum Matching (MaxM), and many others, in both the LOCAL and CONGEST distributed computation models. We present lower bounds for the round complexity of solving parameterized problems in both models, together with optimal and near-optimal upper bounds. Our results extend beyond the scope of parameterized problems. We show that any LOCAL (1+epsilon)-approximation algorithm for the above problems must take Omega(epsilon^{-1}) rounds. Joined with the (epsilon^{-1}log n)^{O(1)} rounds algorithm of [Ghaffari et al., 2017] and the Omega (sqrt{(log n)/(log log n)}) lower bound of [Fabian Kuhn et al., 2016], the lower bounds match the upper bound up to polynomial factors in both parameters. We also show that our parameterized approach reduces the runtime of exact and approximate CONGEST algorithms for MVC and MaxM if the optimal solution is small, without knowing its size beforehand. Finally, we propose the first o(n^2) rounds CONGEST algorithms that approximate MVC within a factor strictly smaller than 2.
Cite as

Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Parameterized Distributed Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.DISC.2019.6,
  author =	{Ben-Basat, Ran and Kawarabayashi, Ken-ichi and Schwartzman, Gregory},
  title =	{{Parameterized Distributed Algorithms}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{6:1--6: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.6},
  URN =		{urn:nbn:de:0030-drops-113135},
  doi =		{10.4230/LIPIcs.DISC.2019.6},
  annote =	{Keywords: Distributed Algorithms, Approximation Algorithms, Parameterized Algorithms}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.135
Distributed Reconfiguration of Maximal Independent Sets

Authors: Keren Censor-Hillel and Mikaël Rabie

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
In this paper, we investigate a distributed maximal independent set (MIS) reconfiguration problem, in which there are two maximal independent sets for which every node is given its membership status, and the nodes need to communicate with their neighbors in order to find a reconfiguration schedule that switches from the first MIS to the second. Such a schedule is a list of independent sets that is restricted by forbidding two neighbors to change their membership status at the same step. In addition, these independent sets should provide some covering guarantee. We show that obtaining an actual MIS (and even a 3-dominating set) in each intermediate step is impossible. However, we provide efficient solutions when the intermediate sets are only required to be independent and 4-dominating, which is almost always possible, as we fully characterize. Consequently, our goal is to pin down the tradeoff between the possible length of the schedule and the number of communication rounds. We prove that a constant length schedule can be found in O(MIS+R32) rounds, where MIS is the complexity of finding an MIS in a worst-case graph and R32 is the complexity of finding a (3,2)-ruling set. For bounded degree graphs, this is O(log^*n) rounds and we show that it is necessary. On the other extreme, we show that with a constant number of rounds we can find a linear length schedule.
Cite as

Keren Censor-Hillel and Mikaël Rabie. Distributed Reconfiguration of Maximal Independent Sets. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 135:1-135:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2019.135,
  author =	{Censor-Hillel, Keren and Rabie, Mika\"{e}l},
  title =	{{Distributed Reconfiguration of Maximal Independent Sets}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{135:1--135:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.135},
  URN =		{urn:nbn:de:0030-drops-107111},
  doi =		{10.4230/LIPIcs.ICALP.2019.135},
  annote =	{Keywords: distributed graph algorithms, reconfiguration, maximal independent set}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.10
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model

Authors: Keren Censor-Hillel, Seri Khoury, and Ami Paz

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires a near-quadratic number of rounds in the CONGEST model, as well as any algorithm for computing the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple linear lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a sub-linear complexity. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.
Cite as

Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2017.10,
  author =	{Censor-Hillel, Keren and Khoury, Seri and Paz, Ami},
  title =	{{Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.10},
  URN =		{urn:nbn:de:0030-drops-79969},
  doi =		{10.4230/LIPIcs.DISC.2017.10},
  annote =	{Keywords: CONGEST, Lower Bounds, Minimum Vertex Cover, Chromatic Number, Weighted APSP}
}
  • Refine by Author
  • 4 Khoury, Seri
  • 2 Censor-Hillel, Keren
  • 2 Kawarabayashi, Ken-ichi
  • 2 Paz, Ami
  • 2 Schwartzman, Gregory
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Approximation algorithms
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Distributed computing models
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 Approximation algorithms
  • 2 Distributed graph algorithms
  • 2 Lower bounds
  • 1 Approximation Algorithms
  • 1 CONGEST
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2019
  • 2 2020
  • 1 2017
  • 1 2023

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