5 Search Results for "Ludwig, Michael"

Document
DOI: 10.4230/LIPIcs.ESA.2019.36
Robustness of Randomized Rumour Spreading

Authors: Rami Daknama, Konstantinos Panagiotou, and Simon Reisser

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
In this work we consider three well-studied broadcast protocols: push, pull and push&pull. A key property of all these models, which is also an important reason for their popularity, is that they are presumed to be very robust, since they are simple, randomized, and, crucially, do not utilize explicitly the global structure of the underlying graph. While sporadic results exist, there has been no systematic theoretical treatment quantifying the robustness of these models. Here we investigate this question with respect to two orthogonal aspects: (adversarial) modifications of the underlying graph and message transmission failures. We explore in particular the following notion of local resilience: beginning with a graph, we investigate up to which fraction of the edges an adversary may delete at each vertex, so that the protocols need significantly more rounds to broadcast the information. Our main findings establish a separation among the three models. On one hand pull is robust with respect to all parameters that we consider. On the other hand, push may slow down significantly, even if the adversary is allowed to modify the degrees of the vertices by an arbitrarily small positive fraction only. Finally, push&pull is robust when no message transmission failures are considered, otherwise it may be slowed down. On the technical side, we develop two novel methods for the analysis of randomized rumour spreading protocols. First, we exploit the notion of self-bounding functions to facilitate significantly the round-based analysis: we show that for any graph the variance of the growth of informed vertices is bounded by its expectation, so that concentration results follow immediately. Second, in order to control adversarial modifications of the graph we make use of a powerful tool from extremal graph theory, namely Szemerédi’s Regularity Lemma.
Cite as

Rami Daknama, Konstantinos Panagiotou, and Simon Reisser. Robustness of Randomized Rumour Spreading. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{daknama_et_al:LIPIcs.ESA.2019.36,
  author =	{Daknama, Rami and Panagiotou, Konstantinos and Reisser, Simon},
  title =	{{Robustness of Randomized Rumour Spreading}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.36},
  URN =		{urn:nbn:de:0030-drops-111571},
  doi =		{10.4230/LIPIcs.ESA.2019.36},
  annote =	{Keywords: Rumour Spreading, Local Resilience, Robustness, Self-bounding Functions, Szemer\'{e}di’s Regularity Lemma}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2019.27
Towards Modeling Geographical Processes with Generative Adversarial Networks (GANs) (Short Paper)

Authors: David Jonietz and Michael Kopp

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)

Abstract
Recently, Generative Adversarial Networks (GANs) have demonstrated great potential for a range of Machine Learning tasks, including synthetic video generation, but have so far not been applied to the domain of modeling geographical processes. In this study, we align these two problems and - motivated by the potential advantages of GANs compared to traditional geosimulation methods - test the capability of GANs to learn a set of underlying rules which determine a geographical process. For this purpose, we turn to Conway’s well-known Game of Life (GoL) as a source for spatio-temporal training data, and further argue for its (and simple variants of it) usefulness as a potential standard training data set for benchmarking generative geographical process models.
Cite as

David Jonietz and Michael Kopp. Towards Modeling Geographical Processes with Generative Adversarial Networks (GANs) (Short Paper). In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 27:1-27:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jonietz_et_al:LIPIcs.COSIT.2019.27,
  author =	{Jonietz, David and Kopp, Michael},
  title =	{{Towards Modeling Geographical Processes with Generative Adversarial Networks (GANs)}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{27:1--27:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.27},
  URN =		{urn:nbn:de:0030-drops-111193},
  doi =		{10.4230/LIPIcs.COSIT.2019.27},
  annote =	{Keywords: GAN, generative modeling, deep learning, geosimulation, game of life}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.36
A Unified Method for Placing Problems in Polylogarithmic Depth

Authors: Andreas Krebs, Nutan Limaye, and Michael Ludwig

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
In this work we consider the term evaluation problem which is, given a term over some algebra and a valid input to the term, computing the value of the term on that input. In contrast to previous methods we allow the algebra to be completely general and consider the problem of obtaining an efficient upper bound for this problem. Many variants of the problems where the algebra is well behaved have been studied. For example, the problem over the Boolean semiring or over the semiring (N,+,*). We extend this line of work. Our efficient term evaluation algorithm then serves as a tool for obtaining polylogarithmic depth upper bounds for various well-studied problems. To demonstrate the utility of our result we show new bounds and reprove known results for a large spectrum of problems. In particular, the applications of the algorithm we consider include (but are not restricted to) arithmetic formula evaluation, word problems for tree and visibly pushdown automata, and various problems related to bounded tree-width and clique-width graphs.
Cite as

Andreas Krebs, Nutan Limaye, and Michael Ludwig. A Unified Method for Placing Problems in Polylogarithmic Depth. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{krebs_et_al:LIPIcs.FSTTCS.2017.36,
  author =	{Krebs, Andreas and Limaye, Nutan and Ludwig, Michael},
  title =	{{A Unified Method for Placing Problems in Polylogarithmic Depth}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.36},
  URN =		{urn:nbn:de:0030-drops-83805},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.36},
  annote =	{Keywords: Polylogarithmic depth, Term evaluation, Parallel algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.594
Visibly Counter Languages and Constant Depth Circuits

Authors: Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC^0 and show that they are contained in FO[+].
Cite as

Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig. Visibly Counter Languages and Constant Depth Circuits. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 594-607, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{krebs_et_al:LIPIcs.STACS.2015.594,
  author =	{Krebs, Andreas and Lange, Klaus-J\"{o}rn and Ludwig, Michael},
  title =	{{Visibly Counter Languages and Constant Depth Circuits}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{594--607},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.594},
  URN =		{urn:nbn:de:0030-drops-49447},
  doi =		{10.4230/LIPIcs.STACS.2015.594},
  annote =	{Keywords: visibly counter automata, constant depth circuits, AC0, FO\lbrack+\rbrack}
}
Document
DOI: 10.4230/DagSemProc.05462.5
05462 Session Summary – "Cross Cutting Concerns"

Authors: Heiko Ludwig and Charles Petrie

Published in: Dagstuhl Seminar Proceedings, Volume 5462, Service Oriented Computing (SOC) (2006)

Abstract
A session on cross cutting concerns of Web services necessarily addresses a multitude of domains, unlike the other 'core' working groups focusing on development and life-cycle, foundations, composition, and management. A cross-cutting issue is a topic that relates to a multiple or all of the core subjects but cannot be address in the context of a single core workgroup.
Cite as

Heiko Ludwig and Charles Petrie. 05462 Session Summary – "Cross Cutting Concerns". In Service Oriented Computing (SOC). Dagstuhl Seminar Proceedings, Volume 5462, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ludwig_et_al:DagSemProc.05462.5,
  author =	{Ludwig, Heiko and Petrie, Charles},
  title =	{{05462 Session Summary – "Cross Cutting Concerns"}},
  booktitle =	{Service Oriented Computing (SOC)},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5462},
  editor =	{Francisco Cubera and Bernd J. Kr\"{a}mer and Michael P. Papazoglou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05462.5},
  URN =		{urn:nbn:de:0030-drops-5261},
  doi =		{10.4230/DagSemProc.05462.5},
  annote =	{Keywords: Cross-cutting concerns, semantics, quality of service, definition, business web services, external effectsCross-cutting concerns, semantics, quality o external effects}
}
  • Refine by Author
  • 2 Krebs, Andreas
  • 2 Ludwig, Michael
  • 1 Daknama, Rami
  • 1 Jonietz, David
  • 1 Kopp, Michael
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Neural networks
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 AC0
  • 1 Cross-cutting concerns
  • 1 FO[+]
  • 1 GAN
  • 1 Local Resilience
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2019
  • 1 2006
  • 1 2015
  • 1 2018

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