3 Search Results for "Doerr, Martin"

Document
DOI: 10.4230/LIPIcs.ESA.2020.21
The Minimization of Random Hypergraphs

Authors: Thomas Bläsius, Tobias Friedrich, and Martin Schirneck

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We investigate the maximum-entropy model B_{n,m,p} for random n-vertex, m-edge multi-hypergraphs with expected edge size pn. We show that the expected size of the minimization min(B_{n,m,p}), i.e., the number of inclusion-wise minimal edges of B_{n,m,p}, undergoes a phase transition with respect to m. If m is at most 1/(1-p)^{(1-p)n}, then E[|min(B_{n,m,p})|] is of order Θ(m), while for m ≥ 1/(1-p)^{(1-p+ε)n} for any ε > 0, it is Θ(2^{(H(α) + (1-α) log₂ p) n}/√n). Here, H denotes the binary entropy function and α = - (log_{1-p} m)/n. The result implies that the maximum expected number of minimal edges over all m is Θ((1+p)ⁿ/√n). Our structural findings have algorithmic implications for minimizing an input hypergraph. This has applications in the profiling of relational databases as well as for the Orthogonal Vectors problem studied in fine-grained complexity. We make several technical contributions that are of independent interest in probability. First, we improve the Chernoff-Hoeffding theorem on the tail of the binomial distribution. In detail, we show that for a binomial variable Y ∼ Bin(n,p) and any 0 < x < p, it holds that P[Y ≤ xn] = Θ(2^{-D(x‖p) n}/√n), where D is the binary Kullback-Leibler divergence between Bernoulli distributions. We give explicit upper and lower bounds on the constants hidden in the big-O notation that hold for all n. Secondly, we establish the fact that the probability of a set of cardinality i being minimal after m i.i.d. maximum-entropy trials exhibits a sharp threshold behavior at i^* = n + log_{1-p} m.
Cite as

Thomas Bläsius, Tobias Friedrich, and Martin Schirneck. The Minimization of Random Hypergraphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2020.21,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Schirneck, Martin},
  title =	{{The Minimization of Random Hypergraphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.21},
  URN =		{urn:nbn:de:0030-drops-128871},
  doi =		{10.4230/LIPIcs.ESA.2020.21},
  annote =	{Keywords: Chernoff-Hoeffding theorem, maximum entropy, maximization, minimization, phase transition, random hypergraphs}
}
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-dev.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}
}
Document
DOI: 10.4230/DagSemProc.04391.22
The CIDOC CRM, an Ontological Approach to Schema Heterogeneity

Authors: Martin Doerr

Published in: Dagstuhl Seminar Proceedings, Volume 4391, Semantic Interoperability and Integration (2005)

Abstract
The CIDOC Conceptual Reference Model (CRM), now ISO/CD21127, is a core ontology that aims at enabling information exchange and integration between heterogeneous sources of cultural heritage information, archives and libraries. It provides semantic definitions and clarifications needed to transform disparate, heterogeneous information sources into a coherent global resource, be it within a larger institution, in intranets or on the Internet. It is argued that such an ontology is property-centric, compact and highly generic, in contrast to terminological systems. The presentation will demonstrate how such a well-crafted core ontology can help to achieve a very high precision of schema integration at reasonable cost in a huge, diverse domain. It is further argued that such ontologies are widely reusable and adaptable to other domains which makes their development cost effective.
Cite as

Martin Doerr. The CIDOC CRM, an Ontological Approach to Schema Heterogeneity. In Semantic Interoperability and Integration. Dagstuhl Seminar Proceedings, Volume 4391, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{doerr:DagSemProc.04391.22,
  author =	{Doerr, Martin},
  title =	{{The CIDOC CRM, an Ontological Approach to Schema Heterogeneity}},
  booktitle =	{Semantic Interoperability and Integration},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4391},
  editor =	{Y. Kalfoglou and M. Schorlemmer and A. Sheth and S. Staab and M. Uschold},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04391.22},
  URN =		{urn:nbn:de:0030-drops-355},
  doi =		{10.4230/DagSemProc.04391.22},
  annote =	{Keywords: formal ontologies , knowledge engineering , semantic interoperability , core ontology , information integration , heterogeneous information museums}
}
  • Refine by Author
  • 1 Bläsius, Thomas
  • 1 Doerr, Benjamin
  • 1 Doerr, Martin
  • 1 Friedrich, Tobias
  • 1 Goldberg, Leslie Ann
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Hypergraphs
  • 1 Mathematics of computing → Information theory
  • 1 Mathematics of computing → Random graphs
  • 1 Theory of computation → Random network models

  • Refine by Keyword
  • 1 Chernoff-Hoeffding theorem
  • 1 Distributed consensus
  • 1 core ontology
  • 1 formal ontologies
  • 1 heterogeneous information museums
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2005
  • 1 2010
  • 1 2020

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