2 Search Results for "N�th, Tobias H."


Document
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
Implementing probabilistic description logics: An application to image interpretation

Authors: Ralf Möller and Tobias H. Näth

Published in: Dagstuhl Seminar Proceedings, Volume 8091, Logic and Probability for Scene Interpretation (2008)


Abstract
This paper presents an application of an optimized implementation of a probabilistic description logic defined by Giugno and Lukasiewicz [9] to the domain of image interpretation. This approach extends a description logic with so-called probabilistic constraints to allow for automated reasoning over formal ontologies in combination with probabilistic knowledge. We analyze the performance of current algorithms and investigate new optimization techniques.

Cite as

Ralf Möller and Tobias H. Näth. Implementing probabilistic description logics: An application to image interpretation. In Logic and Probability for Scene Interpretation. Dagstuhl Seminar Proceedings, Volume 8091, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{moller_et_al:DagSemProc.08091.8,
  author =	{M\"{o}ller, Ralf and N\"{a}th, Tobias H.},
  title =	{{Implementing probabilistic description logics: An application to image interpretation}},
  booktitle =	{Logic and Probability for Scene Interpretation},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8091},
  editor =	{Anthony G. Cohn and David C. Hogg and Ralf M\"{o}ller and Bernd Neumann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08091.8},
  URN =		{urn:nbn:de:0030-drops-16186},
  doi =		{10.4230/DagSemProc.08091.8},
  annote =	{Keywords: Probabilistic description logics, image interpretation probabilistic lexicographic entailment}
}
  • Refine by Author
  • 1 Bläsius, Thomas
  • 1 Friedrich, Tobias
  • 1 Möller, Ralf
  • 1 Näth, Tobias H.
  • 1 Schirneck, Martin

  • 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 Probabilistic description logics
  • 1 image interpretation probabilistic lexicographic entailment
  • 1 maximization
  • 1 maximum entropy
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 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