Search Results

Documents authored by Nebel, Markus E.

Document
DOI: 10.4230/LIPIcs.AofA.2026.23
Moment Statistics in the Boltzmann Probability Model

Authors: Markus E. Nebel

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
A rich family of labeled as well as unlabeled combinatorial structures is accessible by using so-called admissible specifications for which direct access to (counting) generating function equations exists. Using methods from analytic combinatorics, this quite often provides access to asymptotics for their coefficients and thus average-case statistics and knowledge on higher moments and distributions of structural parameters. Furthermore, admissible specifications are the foundation for different approaches of random sampling algorithms either uniformly for a fixed size (e.g., by unranking a random rank) or for random sizes in the Boltzmann model. The latter is of special interest for its efficiency in case of approximate size sampling. It is standard to derive asymptotics for moments from coefficients of generating functions for analytical purposes, e.g. using the saddle-point or the 𝒪-transfer method. In this paper we highlight connections between such asymptotics and the values of generating functions as computed for Boltzmann samplers. We show their use to derive fixed-size statistics from random-size Boltzmann samples. Furthermore, we introduce a new approach for the (leading term) average-case (and higher moment) analysis of structural parameters of combinatorial objects that makes the computation of generating function coefficients superfluous.
Cite as

Markus E. Nebel. Moment Statistics in the Boltzmann Probability Model. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{nebel:LIPIcs.AofA.2026.23,
  author =	{Nebel, Markus E.},
  title =	{{Moment Statistics in the Boltzmann Probability Model}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.23},
  URN =		{urn:nbn:de:0030-drops-262944},
  doi =		{10.4230/LIPIcs.AofA.2026.23},
  annote =	{Keywords: Boltzmann model, random sampling, average-case analysis}
}
Document
DOI: 10.4230/DagRep.11.1.1
Scalable Data Structures (Dagstuhl Seminar 21071)

Authors: Gerth Stølting Brodal, John Iacono, Markus E. Nebel, and Vijaya Ramachandran

Published in: Dagstuhl Reports, Volume 11, Issue 1 (2021)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21071 "Scalable Data Structure". Even if the field of data structures is quite mature, new trends and limitations in computer hardware together with the ever-increasing amounts of data that need to be processed raise new questions with respect to efficiency and continuously challenge the existing models of computation. Thermal and electrical power constraints have caused technology to reach "the power wall" with stagnating single processor performance, meaning that all nontrivial applications need to address scalability with multiple processors, a memory hierarchy and other communication challenges. Scalable data structures are pivotal to this process since they form the backbone of the algorithms driving these applications. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
Cite as

Gerth Stølting Brodal, John Iacono, Markus E. Nebel, and Vijaya Ramachandran. Scalable Data Structures (Dagstuhl Seminar 21071). In Dagstuhl Reports, Volume 11, Issue 1, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.11.1.1,
  author =	{Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya},
  title =	{{Scalable Data Structures (Dagstuhl Seminar 21071)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{1},
  editor =	{Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.1.1},
  URN =		{urn:nbn:de:0030-drops-143481},
  doi =		{10.4230/DagRep.11.1.1},
  annote =	{Keywords: algorithms, big data, data structures, GPU computing, large data sets, models of computation, parallel algorithms}
}
Document
DOI: 10.4230/DagRep.6.3.1
Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101)

Authors: Alejandro Lopez-Ortiz, Ulrich Carsten Meyer, Markus E. Nebel, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 6, Issue 3 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16101 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
Cite as

Alejandro Lopez-Ortiz, Ulrich Carsten Meyer, Markus E. Nebel, and Robert Sedgewick. Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101). In Dagstuhl Reports, Volume 6, Issue 3, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{lopezortiz_et_al:DagRep.6.3.1,
  author =	{Lopez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Nebel, Markus E. and Sedgewick, Robert},
  title =	{{Data Structures and Advanced Models of Computation on Big Data (Dagstuhl Seminar 16101)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{3},
  editor =	{Lopez-Ortiz, Alejandro and Meyer, Ulrich Carsten and Nebel, Markus E. and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.3.1},
  URN =		{urn:nbn:de:0030-drops-61457},
  doi =		{10.4230/DagRep.6.3.1},
  annote =	{Keywords: algorithms, big data, cloud services, data structures, external memory methods, information theory, large data sets, streaming, web-scale}
}
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