Search Results

Documents authored by Mehrabian, Abbas

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.26
The String of Diamonds Is Tight for Rumor Spreading

Authors: Omer Angel, Abbas Mehrabian, and Yuval Peres

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
For a rumor spreading protocol, the spread time is defined as the first time that everyone learns the rumor. We compare the synchronous push&pull rumor spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by O(n^{1/3} log^{2/3} n). This improves the O(sqrt n) upper bound of Giakkoupis, Nazari, and Woelfel (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph.
Cite as

Omer Angel, Abbas Mehrabian, and Yuval Peres. The String of Diamonds Is Tight for Rumor Spreading. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 26:1-26:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{angel_et_al:LIPIcs.APPROX-RANDOM.2017.26,
  author =	{Angel, Omer and Mehrabian, Abbas and Peres, Yuval},
  title =	{{The String of Diamonds Is Tight for Rumor Spreading}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{26:1--26:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.26},
  URN =		{urn:nbn:de:0030-drops-75754},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.26},
  annote =	{Keywords: randomized rumor spreading, push\&pull protocol, asynchronous time model, string of diamonds}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.857
It’s a Small World for Random Surfers

Authors: Abbas Mehrabian and Nick Wormald

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We prove logarithmic upper bounds for the diameters of the random-surfer Webgraph model and the PageRank-based selection Webgraph model, confirming the small-world phenomenon holds for them. In the special case when the generated graph is a tree, we get close lower and upper bounds for the diameters of both models.
Cite as

Abbas Mehrabian and Nick Wormald. It’s a Small World for Random Surfers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 857-871, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{mehrabian_et_al:LIPIcs.APPROX-RANDOM.2014.857,
  author =	{Mehrabian, Abbas and Wormald, Nick},
  title =	{{It’s a Small World for Random Surfers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{857--871},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.857},
  URN =		{urn:nbn:de:0030-drops-47437},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.857},
  annote =	{Keywords: random-surfer webgraph model, PageRank-based selection model, smallworld phenomenon, height of random trees, probabilistic analysis, large deviations}
}
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 About DROPS Imprint Privacy Contact