Search Results

Documents authored by Doerr, Benjamin

Document
DOI: 10.4230/DagRep.12.5.17
Estimation-of-Distribution Algorithms: Theory and Applications (Dagstuhl Seminar 22182)

Authors: Josu Ceberio Uribe, Benjamin Doerr, Carsten Witt, and Vicente P. Soloviev

Published in: Dagstuhl Reports, Volume 12, Issue 5 (2022)

Abstract
The Dagstuhl seminar 22182 Estimation-of-Distribution Algorithms: Theory and Practice on May 2-6, 2022 brought together 19 international experts in estimation-of-distribution algorithms (EDAs). Their research ranged from a theoretical perspective, e.g., runtime analysis on synthetic problems, to an applied perspective, e.g., solutions of industrial optimization problems with EDAs. This report documents the program and the outcomes of the seminar.
Cite as

Josu Ceberio Uribe, Benjamin Doerr, Carsten Witt, and Vicente P. Soloviev. Estimation-of-Distribution Algorithms: Theory and Applications (Dagstuhl Seminar 22182). In Dagstuhl Reports, Volume 12, Issue 5, pp. 17-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{uribe_et_al:DagRep.12.5.17,
  author =	{Uribe, Josu Ceberio and Doerr, Benjamin and Witt, Carsten and Soloviev, Vicente P.},
  title =	{{Estimation-of-Distribution Algorithms: Theory and Applications (Dagstuhl Seminar 22182)}},
  pages =	{17--36},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{5},
  editor =	{Uribe, Josu Ceberio and Doerr, Benjamin and Witt, Carsten and Soloviev, Vicente P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.5.17},
  URN =		{urn:nbn:de:0030-drops-174421},
  doi =		{10.4230/DagRep.12.5.17},
  annote =	{Keywords: estimation-of-distribution algorithms, heuristic search and optimization, machine learning, probabilistic model building}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.138
Randomized Rumor Spreading Revisited

Authors: Benjamin Doerr and Anatolii Kostrygin

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We develop a simple and generic method to analyze randomized rumor spreading processes in fully connected networks. In contrast to all previous works, which heavily exploit the precise definition of the process under investigation, we only need to understand the probability and the covariance of the events that uninformed nodes become informed. This universality allows us to easily analyze the classic push, pull, and push-pull protocols both in their pure version and in several variations such as messages failing with constant probability or nodes calling a random number of others each round. Some dynamic models can be analyzed as well, e.g., when the network is a G(n,p) random graph sampled independently each round [Clementi et al. (ESA 2013)]. Despite this generality, our method determines the expected rumor spreading time precisely apart from additive constants, which is more precise than almost all previous works. We also prove tail bounds showing that a deviation from the expectation by more than an additive number of r rounds occurs with probability at most exp(-Omega(r)). We further use our method to discuss the common assumption that nodes can answer any number of incoming calls. We observe that the restriction that only one call can be answered leads to a significant increase of the runtime of the push-pull protocol. In particular, the double logarithmic end phase of the process now takes logarithmic time. This also increases the message complexity from the asymptotically optimal Theta(n*log(log(n))) [Karp, Shenker, Schindelhauer, Vöcking (FOCS 2000)] to Theta(n*log(n)). We propose a simple variation of the push-pull protocol that reverts back to the double logarithmic end phase and thus to the $\Theta(n*log(log(n))) message complexity.
Cite as

Benjamin Doerr and Anatolii Kostrygin. Randomized Rumor Spreading Revisited. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 138:1-138:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{doerr_et_al:LIPIcs.ICALP.2017.138,
  author =	{Doerr, Benjamin and Kostrygin, Anatolii},
  title =	{{Randomized Rumor Spreading Revisited}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{138:1--138:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.138},
  URN =		{urn:nbn:de:0030-drops-73798},
  doi =		{10.4230/LIPIcs.ICALP.2017.138},
  annote =	{Keywords: Epidemic algorithm, rumor spreading, dynamic graph}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.150
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem

Authors: Benjamin Doerr and Marvin Künnemann

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
The cryptogenography problem, introduced by Brody, Jakobsen, Scheder, and Winkler (ITCS 2014), is to collaboratively leak a piece of information known to only one member of a group (i) without revealing who was the origin of this information and (ii) without any private communication, neither during the process nor before. Despite several deep structural results, even the smallest case of leaking one bit of information present at one of two players is not well understood. Brody et al. gave a 2-round protocol enabling the two players to succeed with probability 1/3 and showed the hardness result that no protocol can give a success probability of more than 3/8. In this work, we show that neither bound is tight. Our new hardness result, obtained by a different application of the concavity method used also in the previous work, states that a success probability of better than 0.3672 is not possible. Using both theoretical and numerical approaches, we improve the lower bound to 0.3384, that is, give a protocol leading to this success probability. To ease the design of new protocols, we prove an equivalent formulation of the cryptogenography problem as solitaire vector splitting game. Via an automated game tree search, we find good strategies for this game. We then translate the splits that occurred in this strategy into inequalities relating position values and use an LP solver to find an optimal solution for these inequalities. This gives slightly better game values, but more importantly, also a more compact representation of the protocol and a way to easily verify the claimed quality of the protocol. Unfortunately, already the smallest protocol we found that beats the previous 1/3 success probability takes up 16 rounds of communication. The protocol leading to the bound of 0.3384 even in a compact representation consists of 18248 game states. These numbers suggest that the task of finding good protocols for the cryptogenography problem as well as understanding their structure is harder than what the simple problem formulation suggests.
Cite as

Benjamin Doerr and Marvin Künnemann. Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 150:1-150:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{doerr_et_al:LIPIcs.ICALP.2016.150,
  author =	{Doerr, Benjamin and K\"{u}nnemann, Marvin},
  title =	{{Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{150:1--150:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.150},
  URN =		{urn:nbn:de:0030-drops-62946},
  doi =		{10.4230/LIPIcs.ICALP.2016.150},
  annote =	{Keywords: randomized protocols, anonymous communication, computer-aided proofs, solitaire games}
}
Document
DOI: 10.4230/DagRep.3.7.1
Theory of Evolutionary Algorithms (Dagstuhl Seminar 13271)

Authors: Benjamin Doerr, Nikolaus Hansen, Jonathan L. Shapiro, and L. Darrell Whitley

Published in: Dagstuhl Reports, Volume 3, Issue 7 (2013)

Abstract
This report documents the talks and discussions of Dagstuhl Seminar 13271 "Theory of Evolutionary Algorithms". This seminar, now in its 7th edition, is the main meeting point of the highly active theory of randomized search heuristics subcommunities in Australia, Asia, North America and Europe. Topics intensively discussed include a complexity theory for randomized search heuristics, evolutionary computation in noisy settings, the drift analysis technique, and parallel evolutionary computation.
Cite as

Benjamin Doerr, Nikolaus Hansen, Jonathan L. Shapiro, and L. Darrell Whitley. Theory of Evolutionary Algorithms (Dagstuhl Seminar 13271). In Dagstuhl Reports, Volume 3, Issue 7, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{doerr_et_al:DagRep.3.7.1,
  author =	{Doerr, Benjamin and Hansen, Nikolaus and Shapiro, Jonathan L. and Whitley, L. Darrell},
  title =	{{Theory of Evolutionary Algorithms (Dagstuhl Seminar 13271)}},
  pages =	{1--28},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{7},
  editor =	{Doerr, Benjamin and Hansen, Nikolaus and Shapiro, Jonathan L. and Whitley, L. Darrell},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.7.1},
  URN =		{urn:nbn:de:0030-drops-42603},
  doi =		{10.4230/DagRep.3.7.1},
  annote =	{Keywords: evolutionary algorithms, optimization, search heuristics, algorithms, artificial intelligence}
}
Document
DOI: 10.4230/DagRep.3.1.94
Epidemic Algorithms and Processes: From Theory to Applications (Dagstuhl Seminar 13042)

Authors: Benjamin Doerr, Robert Elsässer, and Pierre Fraigniaud

Published in: Dagstuhl Reports, Volume 3, Issue 1 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13042 "Epidemic Algorithms and Processes: From Theory to Applications", which took place from January 20 to 25, 2013 at Schloss Dagstuhl - Leibniz Center for Informatics. Several research topics were covered by the seminar participants, including scientists working in Theoretical Computer Science, as well as researchers from the more practical area of Computer Systems. Most of the participants presented their recent results on the topic of the seminar, as well as some challenging new directions and open problems. The presentations contained a description of the main research area for a wide audience. During the seminar, ample time was reserved for informal discussions between participants working on different topics. In our executive summary, we describe the main field of the seminar, as well as our goals in general. Then, we present the abstracts of the presentations given during the seminar.
Cite as

Benjamin Doerr, Robert Elsässer, and Pierre Fraigniaud. Epidemic Algorithms and Processes: From Theory to Applications (Dagstuhl Seminar 13042). In Dagstuhl Reports, Volume 3, Issue 1, pp. 94-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{doerr_et_al:DagRep.3.1.94,
  author =	{Doerr, Benjamin and Els\"{a}sser, Robert and Fraigniaud, Pierre},
  title =	{{Epidemic Algorithms and Processes: From Theory to Applications (Dagstuhl Seminar 13042)}},
  pages =	{94--110},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{1},
  editor =	{Doerr, Benjamin and Els\"{a}sser, Robert and Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.1.94},
  URN =		{urn:nbn:de:0030-drops-40104},
  doi =		{10.4230/DagRep.3.1.94},
  annote =	{Keywords: Message dissemination, Epidemic spreading, Dynamic spreading processes}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.441
Playing Mastermind With Constant-Size Memory

Authors: Benjamin Doerr and Carola Winzen

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We analyze the classic board game of Mastermind with n holes and a constant number of colors. The classic result of Chvatal (Combinatorica 3 (1983), 325-329) states that the codebreaker can find the secret code with Theta(n / log n) questions. We show that this bound remains valid if the codebreaker may only store a constant number of guesses and answers. In addition to an intrinsic interest in this question, our result also disproves a conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006), 525-544) on the memory-restricted black-box complexity of the OneMax function class.
Cite as

Benjamin Doerr and Carola Winzen. Playing Mastermind With Constant-Size Memory. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 441-452, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{doerr_et_al:LIPIcs.STACS.2012.441,
  author =	{Doerr, Benjamin and Winzen, Carola},
  title =	{{Playing Mastermind With Constant-Size Memory}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{441--452},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.441},
  URN =		{urn:nbn:de:0030-drops-34112},
  doi =		{10.4230/LIPIcs.STACS.2012.441},
  annote =	{Keywords: Algorithms, Mastermind, black-box complexity, memory-restricted algorithms, query complexity}
}
Document
DOI: 10.4230/DagSemProc.09371.6
Stabilizing Consensus with the Power of Two Choices

Authors: Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract
Consensus problems occur in many contexts and have therefore been intensively studied in the past. In the standard consensus problem there are n processes with possibly different input values and the goal is to eventually reach a point at which all processes commit to exactly one of these values. We are studying a slight variant of the consensus problem called the stabilizing consensus problem. In this problem, we do not require that each process commits to a final value at some point, but that eventually they arrive at a common value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Coming up with a self-stabilizing rule is easy without adversarial involvement, but we allow some T-bounded adversary to manipulate any T processes at any time. In this situation, a perfect consensus is impossible to reach, so we only require that there is a time point t and value v so that at any point after t, all but up to O(T) processes agree on v, which we call an almost stable consensus. As we will demonstrate, there is a surprisingly simple rule for the standard message passing model that just needs O(log n loglog n) time for any sqrt{n}-bounded adversary and just O(log n) time without adversarial involvement, with high probability, to reach an (almost) stable consensus from any initial state. A stable consensus is reached, with high probability, in the absence of adversarial involvement.
Cite as

Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing Consensus with the Power of Two Choices. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{doerr_et_al:DagSemProc.09371.6,
  author =	{Doerr, Benjamin and Goldberg, Leslie Ann and Minder, Lorenz and Sauerwald, Thomas and Scheideler, Christian},
  title =	{{Stabilizing Consensus with the Power of Two Choices}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.6},
  URN =		{urn:nbn:de:0030-drops-24290},
  doi =		{10.4230/DagSemProc.09371.6},
  annote =	{Keywords: Distributed consensus}
}
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