3 Search Results for "Gebhard, Oliver"

Document
DOI: 10.4230/LIPIcs.DISC.2025.27
On the h-Majority Dynamics with Many Opinions

Authors: Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We present the first upper bound on the convergence time to consensus of the well-known h-majority dynamics with k opinions, in the synchronous setting, for h and k that are both non-constant values. We suppose that, at the beginning of the process, there is some initial additive bias towards some plurality opinion, that is, there is an opinion that is supported by x nodes while any other opinion is supported by strictly fewer nodes. We prove that, with high probability, if the bias is ω(√x) and the initial plurality opinion is supported by at least x = ω(log n) nodes, then the process converges to plurality consensus in O(log n) rounds whenever h = ω(n log n / x). A main corollary is the following: if k = o(n / log n) and the process starts from an almost-balanced configuration with an initial bias of magnitude ω(√{n/k}) towards the initial plurality opinion, then any function h = ω(k log n) suffices to guarantee convergence to consensus in O(log n) rounds, with high probability. Our upper bound shows that the lower bound of Ω(k / h²) rounds to reach consensus given by Becchetti et al. (2017) cannot be pushed further than Ω̃(k / h). Moreover, the bias we require is asymptotically smaller than the Ω(√{nlog n}) bias that guarantees plurality consensus in the 3-majority dynamics: in our case, the required bias is at most any (arbitrarily small) function in ω(√x) for any value of k ≥ 2.
Cite as

Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale. On the h-Majority Dynamics with Many Opinions. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 27:1-27:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{damore_et_al:LIPIcs.DISC.2025.27,
  author =	{d'Amore, Francesco and D'Archivio, Niccol\`{o} and Giakkoupis, George and Natale, Emanuele},
  title =	{{On the h-Majority Dynamics with Many Opinions}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{27:1--27:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.27},
  URN =		{urn:nbn:de:0030-drops-248448},
  doi =		{10.4230/LIPIcs.DISC.2025.27},
  annote =	{Keywords: Distributed Algorithms, Randomized Algorithms, Markov Chains, Consensus Problem, Opinion dynamics, Plurality Consensus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.23
On the Hierarchy of Distributed Majority Protocols

Authors: Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
We study the consensus problem among n agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called j-Majority: when activated, every agent samples j other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: (j+1)-Majority (for j > 1) converges stochastically faster than j-Majority for any initial opinion configuration. In our analysis we use Strassen’s Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [PODC 2017].
Cite as

Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the Hierarchy of Distributed Majority Protocols. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berenbrink_et_al:LIPIcs.OPODIS.2022.23,
  author =	{Berenbrink, Petra and Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Kaaser, Dominik and Rau, Malin},
  title =	{{On the Hierarchy of Distributed Majority Protocols}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.23},
  URN =		{urn:nbn:de:0030-drops-176434},
  doi =		{10.4230/LIPIcs.OPODIS.2022.23},
  annote =	{Keywords: Consensus, Majority, Hierarchy, Stochastic Dominance, Population Protocols, Gossip Model, Strassen’s Theorem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.43
Information-Theoretic and Algorithmic Thresholds for Group Testing

Authors: Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Philipp Loick

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

Abstract
In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [Aldridge et al. 2016] the individuals are assigned to test groups randomly, with every individual joining an equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [Aldridge et al. 2014, Johnson et al. 2019].
Cite as

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Philipp Loick. Information-Theoretic and Algorithmic Thresholds for Group Testing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cojaoghlan_et_al:LIPIcs.ICALP.2019.43,
  author =	{Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Loick, Philipp},
  title =	{{Information-Theoretic and Algorithmic Thresholds for Group Testing}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{43:1--43: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.43},
  URN =		{urn:nbn:de:0030-drops-106196},
  doi =		{10.4230/LIPIcs.ICALP.2019.43},
  annote =	{Keywords: Group testing problem, phase transitions, information theory, efficient algorithms, sharp threshold, Bayesian inference}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023
  • 1 2019

  • Refine by Author
  • 2 Coja-Oghlan, Amin
  • 2 Gebhard, Oliver
  • 2 Hahn-Klimroth, Max
  • 1 Berenbrink, Petra
  • 1 D'Archivio, Niccolò
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms
  • 1 Applied computing → Systems biology
  • 1 Mathematics of computing → Markov processes
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Stochastic processes
  • Show More...

  • Refine by Keyword
  • 1 Bayesian inference
  • 1 Consensus
  • 1 Consensus Problem
  • 1 Distributed Algorithms
  • 1 Gossip Model
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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