4 Search Results for "Sylvester, John"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.86
Rumors with Changing Credibility

Authors: Charlotte Out, Nicolás Rivera, Thomas Sauerwald, and John Sylvester

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Randomized rumor spreading processes diffuse information on an undirected graph and have been widely studied. In this work, we present a generic framework for analyzing a broad class of such processes on regular graphs. Our analysis is protocol-agnostic, as it only requires the expected proportion of newly informed vertices in each round to be bounded, and a natural negative correlation property. This framework allows us to analyze various protocols, including PUSH, PULL, and PUSH-PULL, thereby extending prior research. Unlike previous work, our framework accommodates message failures at any time t ≥ 0 with a probability of 1-q(t), where the credibility q(t) is any function of time. This enables us to model real-world scenarios in which the transmissibility of rumors may fluctuate, as seen in the spread of "fake news" and viruses. Additionally, our framework is sufficiently broad to cover dynamic graphs.
Cite as

Charlotte Out, Nicolás Rivera, Thomas Sauerwald, and John Sylvester. Rumors with Changing Credibility. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 86:1-86:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{out_et_al:LIPIcs.ITCS.2024.86,
  author =	{Out, Charlotte and Rivera, Nicol\'{a}s and Sauerwald, Thomas and Sylvester, John},
  title =	{{Rumors with Changing Credibility}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{86:1--86:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.86},
  URN =		{urn:nbn:de:0030-drops-196149},
  doi =		{10.4230/LIPIcs.ITCS.2024.86},
  annote =	{Keywords: Rumor spreading, epidemic algorithms, "fake news"}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.30
Cover and Hitting Times of Hyperbolic Random Graphs

Authors: Marcos Kiwi, Markus Schepers, and John Sylvester

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

Abstract
We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range (2,3). In particular, we focus on the expected times for a random walk to hit a given vertex or visit, i.e. cover, all vertices. We show that up to multiplicative constants: the cover time is n(log n)², the maximum hitting time is nlog n, and the average hitting time is n. The first two results hold in expectation and a.a.s. and the last in expectation (with respect to the HRG). We prove these results by determining the effective resistance either between an average vertex and the well-connected "center" of HRGs or between an appropriately chosen collection of extremal vertices. We bound the effective resistance by the energy dissipated by carefully designed network flows associated to a tiling of the hyperbolic plane on which we overlay a forest-like structure.
Cite as

Marcos Kiwi, Markus Schepers, and John Sylvester. Cover and Hitting Times of Hyperbolic Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kiwi_et_al:LIPIcs.APPROX/RANDOM.2022.30,
  author =	{Kiwi, Marcos and Schepers, Markus and Sylvester, John},
  title =	{{Cover and Hitting Times of Hyperbolic Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.30},
  URN =		{urn:nbn:de:0030-drops-171523},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.30},
  annote =	{Keywords: Random walk, hyperbolic random graph, cover time, hitting time, average hitting time, target time, effective resistance, Kirchhoff index}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.107
Multiple Random Walks on Graphs: Mixing Few to Cover Many

Authors: Nicolás Rivera, Thomas Sauerwald, and John Sylvester

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

Abstract
Random walks on graphs are an essential primitive for many randomised algorithms and stochastic processes. It is natural to ask how much can be gained by running k multiple random walks independently and in parallel. Although the cover time of multiple walks has been investigated for many natural networks, the problem of finding a general characterisation of multiple cover times for worst-case start vertices (posed by Alon, Avin, Koucký, Kozma, Lotker, and Tuttle in 2008) remains an open problem. First, we improve and tighten various bounds on the stationary cover time when k random walks start from vertices sampled from the stationary distribution. For example, we prove an unconditional lower bound of Ω((n/k) log n) on the stationary cover time, holding for any n-vertex graph G and any 1 ≤ k = o(nlog n). Secondly, we establish the stationary cover times of multiple walks on several fundamental networks up to constant factors. Thirdly, we present a framework characterising worst-case cover times in terms of stationary cover times and a novel, relaxed notion of mixing time for multiple walks called the partial mixing time. Roughly speaking, the partial mixing time only requires a specific portion of all random walks to be mixed. Using these new concepts, we can establish (or recover) the worst-case cover times for many networks including expanders, preferential attachment graphs, grids, binary trees and hypercubes.
Cite as

Nicolás Rivera, Thomas Sauerwald, and John Sylvester. Multiple Random Walks on Graphs: Mixing Few to Cover Many. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 107:1-107:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rivera_et_al:LIPIcs.ICALP.2021.107,
  author =	{Rivera, Nicol\'{a}s and Sauerwald, Thomas and Sylvester, John},
  title =	{{Multiple Random Walks on Graphs: Mixing Few to Cover Many}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{107:1--107:16},
  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.107},
  URN =		{urn:nbn:de:0030-drops-141764},
  doi =		{10.4230/LIPIcs.ICALP.2021.107},
  annote =	{Keywords: Multiple Random walks, Markov Chains, Random Walks, Cover Time}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.76
Choice and Bias in Random Walks

Authors: Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, and John Sylvester

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We analyse the following random walk process inspired by the power-of-two-choice paradigm: starting from a given vertex, at each step, unlike the simple random walk (SRW) that always moves to a randomly chosen neighbour, we have the choice between two uniformly and independently chosen neighbours. We call this process the choice random walk (CRW). We first prove that for any graph, there is a strategy for the CRW that visits any given vertex in expected time ?(|E|). Then we introduce a general tool that quantifies by how much the probability of a rare event in the simple random walk can be boosted under a suitable CRW strategy. We believe this result to be of independent interest, and apply it here to derive an almost optimal ?(n log log n) bound for the cover time of bounded-degree expanders. This tool also applies to so-called biased walks, and allows us to make progress towards a conjecture of Azar et al. [STOC 1992]. Finally, we prove the following dichotomy: computing an optimal strategy to minimise the hitting time of a vertex takes polynomial time, whereas computing one to minimise the cover time is NP-hard.
Cite as

Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, and John Sylvester. Choice and Bias in Random Walks. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 76:1-76:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{georgakopoulos_et_al:LIPIcs.ITCS.2020.76,
  author =	{Georgakopoulos, Agelos and Haslegrave, John and Sauerwald, Thomas and Sylvester, John},
  title =	{{Choice and Bias in Random Walks}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{76:1--76:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.76},
  URN =		{urn:nbn:de:0030-drops-117612},
  doi =		{10.4230/LIPIcs.ITCS.2020.76},
  annote =	{Keywords: Power of Two Choices, Markov Chains, Random Walks, Cover Time, Markov Decision Processes}
}
  • Refine by Author
  • 4 Sylvester, John
  • 3 Sauerwald, Thomas
  • 2 Rivera, Nicolás
  • 1 Georgakopoulos, Agelos
  • 1 Haslegrave, John
  • Show More...

  • Refine by Classification
  • 4 Mathematics of computing → Stochastic processes
  • 3 Theory of computation → Random walks and Markov chains
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Random network models

  • Refine by Keyword
  • 2 Cover Time
  • 2 Markov Chains
  • 2 Random Walks
  • 1 "fake news"
  • 1 Kirchhoff index
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021
  • 1 2022
  • 1 2024

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