49 Search Results for "Wild, Sebastian"

Volume

LIPIcs, Volume 302

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

AofA 2024, June 17-21, 2024, University of Bath, UK

Editors: Cécile Mailler and Sebastian Wild

Document
Complete Volume
DOI: 10.4230/LIPIcs.AofA.2024
LIPIcs, Volume 302, AofA 2024, Complete Volume

Authors: Cécile Mailler and Sebastian Wild

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
LIPIcs, Volume 302, AofA 2024, Complete Volume
Cite as

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 1-458, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{mailler_et_al:LIPIcs.AofA.2024,
  title =	{{LIPIcs, Volume 302, AofA 2024, Complete Volume}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{1--458},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024},
  URN =		{urn:nbn:de:0030-drops-204341},
  doi =		{10.4230/LIPIcs.AofA.2024},
  annote =	{Keywords: LIPIcs, Volume 302, AofA 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.AofA.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Cécile Mailler and Sebastian Wild

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mailler_et_al:LIPIcs.AofA.2024.0,
  author =	{Mailler, C\'{e}cile and Wild, Sebastian},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.0},
  URN =		{urn:nbn:de:0030-drops-204353},
  doi =		{10.4230/LIPIcs.AofA.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.1
Fringe Trees for Random Trees with Given Vertex Degrees

Authors: Gabriel Berzunza Ojeda, Cecilia Holmgren, and Svante Janson

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We prove that the number of fringe subtrees, isomorphic to a given tree, in uniformly random trees with given vertex degrees, asymptotically follows a normal distribution. As an application, we establish the same asymptotic normality for random simply generated trees (conditioned Galton-Watson trees). Our approach relies on an extension of Gao and Wormald’s (2004) theorem to the multivariate setting.
Cite as

Gabriel Berzunza Ojeda, Cecilia Holmgren, and Svante Janson. Fringe Trees for Random Trees with Given Vertex Degrees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berzunzaojeda_et_al:LIPIcs.AofA.2024.1,
  author =	{Berzunza Ojeda, Gabriel and Holmgren, Cecilia and Janson, Svante},
  title =	{{Fringe Trees for Random Trees with Given Vertex Degrees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{1:1--1:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.1},
  URN =		{urn:nbn:de:0030-drops-204369},
  doi =		{10.4230/LIPIcs.AofA.2024.1},
  annote =	{Keywords: Conditioned Galton-Watson trees, fringe trees, simply generated trees, uniformly random trees with given vertex degrees}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.2
Enumeration and Succinct Encoding of AVL Trees

Authors: Jeremy Chizewer, Stephen Melczer, J. Ian Munro, and Ava Pun

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We use a novel decomposition to create succinct data structures - supporting a wide range of operations on static trees in constant time - for a variety of tree classes, extending results of Munro, Nicholson, Benkner, and Wild. Motivated by the class of AVL trees, we further derive asymptotics for the information-theoretic lower bound on the number of bits needed to store tree classes whose generating functions satisfy certain functional equations. In particular, we prove that AVL trees require approximately 0.938 bits per node to encode.
Cite as

Jeremy Chizewer, Stephen Melczer, J. Ian Munro, and Ava Pun. Enumeration and Succinct Encoding of AVL Trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chizewer_et_al:LIPIcs.AofA.2024.2,
  author =	{Chizewer, Jeremy and Melczer, Stephen and Munro, J. Ian and Pun, Ava},
  title =	{{Enumeration and Succinct Encoding of AVL Trees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.2},
  URN =		{urn:nbn:de:0030-drops-204376},
  doi =		{10.4230/LIPIcs.AofA.2024.2},
  annote =	{Keywords: AVL trees, analytic combinatorics, succinct data structures, enumeration}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.3
Maximal Number of Subword Occurrences in a Word

Authors: Wenjie Fang

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We consider the number of occurrences of subwords (non-consecutive sub-sequences) in a given word. We first define the notion of subword entropy of a given word that measures the maximal number of occurrences among all possible subwords. We then give upper and lower bounds of minimal subword entropy for words of fixed length in a fixed alphabet, and also showing that minimal subword entropy per letter has a limit value. A better upper bound of minimal subword entropy for a binary alphabet is then given by looking at certain families of periodic words. We also give some conjectures based on experimental observations.
Cite as

Wenjie Fang. Maximal Number of Subword Occurrences in a Word. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fang:LIPIcs.AofA.2024.3,
  author =	{Fang, Wenjie},
  title =	{{Maximal Number of Subword Occurrences in a Word}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{3:1--3:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.3},
  URN =		{urn:nbn:de:0030-drops-204387},
  doi =		{10.4230/LIPIcs.AofA.2024.3},
  annote =	{Keywords: Subword occurrence, subword entropy, enumeration, periodic words}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.4
Sparsification of Phylogenetic Covariance Matrices of k-Regular Trees

Authors: Sean Svihla and Manuel E. Lladser

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
Consider a tree T = (V,E) with root ∘ and an edge length function 𝓁:E → ℝ_+. The phylogenetic covariance matrix of T is the matrix C with rows and columns indexed by L, the leaf set of T, with entries C(i,j): = ∑_{e ∈ [i∧ j,o]}𝓁(e), for each i,j ∈ L. Recent work [Gorman & Lladser 2023] has shown that the phylogenetic covariance matrix of a large but random binary tree T is significantly sparsified, with overwhelmingly high probability, under a change-of-basis to the so-called Haar-like wavelets of T. Notably, this finding enables manipulating the spectrum of covariance matrices of large binary trees without the necessity to store them in computer memory but instead performing two post-order traversals of the tree [Gorman & Lladser 2023]. Building on the methods of the aforesaid paper, this manuscript further advances their sparsification result to encompass the broader class of k-regular trees, for any given k ≥ 2. This extension is achieved by refining existing asymptotic formulas for the mean and variance of the internal path length of random k-regular trees, utilizing hypergeometric function properties and identities.
Cite as

Sean Svihla and Manuel E. Lladser. Sparsification of Phylogenetic Covariance Matrices of k-Regular Trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{svihla_et_al:LIPIcs.AofA.2024.4,
  author =	{Svihla, Sean and Lladser, Manuel E.},
  title =	{{Sparsification of Phylogenetic Covariance Matrices of k-Regular Trees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.4},
  URN =		{urn:nbn:de:0030-drops-204399},
  doi =		{10.4230/LIPIcs.AofA.2024.4},
  annote =	{Keywords: cophenetic matrix, Haar-like wavelets, hierarchical data, hypergeometric functions, metagenomics, phylogenetic covariance matrix, sparsification, ultrametric matrix}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.5
Bit-Array-Based Alternatives to HyperLogLog

Authors: Svante Janson, Jérémie Lumbroso, and Robert Sedgewick

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We present a family of algorithms for the problem of estimating the number of distinct items in an input stream that are simple to implement and are appropriate for practical applications. Our algorithms are a logical extension of the series of algorithms developed by Flajolet and his coauthors starting in 1983 that culminated in the widely used HyperLogLog algorithm. These algorithms divide the input stream into M substreams and lead to a time-accuracy tradeoff where a constant number of bits per substream are saved to achieve a relative accuracy proportional to 1/√M. Our algorithms use just one or two bits per substream. Their effectiveness is demonstrated by a proof of approximate normality, with explicit expressions for standard errors that inform parameter settings and allow proper quantitative comparisons with other methods. Hypotheses about performance are validated through experiments using a realistic input stream, with the conclusion that our algorithms are more accurate than HyperLogLog when using the same amount of memory, and they use two-thirds as much memory as HyperLogLog to achieve a given accuracy.
Cite as

Svante Janson, Jérémie Lumbroso, and Robert Sedgewick. Bit-Array-Based Alternatives to HyperLogLog. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{janson_et_al:LIPIcs.AofA.2024.5,
  author =	{Janson, Svante and Lumbroso, J\'{e}r\'{e}mie and Sedgewick, Robert},
  title =	{{Bit-Array-Based Alternatives to HyperLogLog}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.5},
  URN =		{urn:nbn:de:0030-drops-204402},
  doi =		{10.4230/LIPIcs.AofA.2024.5},
  annote =	{Keywords: Cardinality estimation, sketching, Hyperloglog}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.6
Phase Transition for Tree-Rooted Maps

Authors: Marie Albenque, Éric Fusy, and Zéphyr Salvy

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We introduce a model of tree-rooted planar maps weighted by their number of 2-connected blocks. We study its enumerative properties and prove that it undergoes a phase transition. We give the distribution of the size of the largest 2-connected blocks in the three regimes (subcritical, critical and supercritical) and further establish that the scaling limit is the Brownian Continuum Random Tree in the critical and supercritical regimes, with respective rescalings √{n/log(n)} and √n.
Cite as

Marie Albenque, Éric Fusy, and Zéphyr Salvy. Phase Transition for Tree-Rooted Maps. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albenque_et_al:LIPIcs.AofA.2024.6,
  author =	{Albenque, Marie and Fusy, \'{E}ric and Salvy, Z\'{e}phyr},
  title =	{{Phase Transition for Tree-Rooted Maps}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.6},
  URN =		{urn:nbn:de:0030-drops-204413},
  doi =		{10.4230/LIPIcs.AofA.2024.6},
  annote =	{Keywords: Asymptotic Enumeration, Planar maps, Random trees, Phase transition}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.7
Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models

Authors: Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
Composition schemes are ubiquitous in combinatorics, statistical mechanics and probability theory. We give a unifying explanation to various phenomena observed in the combinatorial and statistical physics literature in the context of q-enumeration (this is a model where objects with a parameter of value k have a Gibbs measure/Boltzmann weight q^k). For structures enumerated by a composition scheme, we prove a phase transition for any parameter having such a Gibbs measure: for a critical value q = q_c, the limit law of the parameter is a two-parameter Mittag-Leffler distribution, while it is Gaussian in the supercritical regime (q > q_c), and it is a Boltzmann distribution in the subcritical regime (0 < q < q_c). We apply our results to fundamental statistics of lattice paths and quarter-plane walks. We also explain previously observed limit laws for pattern-restricted permutations, and a phenomenon uncovered by Krattenthaler for the wall contacts in watermelons.
Cite as

Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner. Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2024.7,
  author =	{Banderier, Cyril and Kuba, Markus and Wagner, Stephan and Wallner, Michael},
  title =	{{Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.7},
  URN =		{urn:nbn:de:0030-drops-204427},
  doi =		{10.4230/LIPIcs.AofA.2024.7},
  annote =	{Keywords: Composition schemes, q-enumeration, generating functions, Gibbs distribution, phase transitions, limit laws, Mittag-Leffler distribution, chi distribution, Boltzmann distribution}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.8
Galled Tree-Child Networks

Authors: Yu-Sheng Chang, Michael Fuchs, and Guan-Ru Yu

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We propose the class of galled tree-child networks which is obtained as intersection of the classes of galled networks and tree-child networks. For the latter two classes, (asymptotic) counting results and stochastic results have been proved with very different methods. We show that a counting result for the class of galled tree-child networks follows with similar tools as used for galled networks, however, the result has a similar pattern as the one for tree-child networks. In addition, we also consider the (suitably scaled) numbers of reticulation nodes of random galled tree-child networks and show that they are asymptotically normal distributed. This is in contrast to the limit laws of the corresponding quantities for galled networks and tree-child networks which have been both shown to be discrete.
Cite as

Yu-Sheng Chang, Michael Fuchs, and Guan-Ru Yu. Galled Tree-Child Networks. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.AofA.2024.8,
  author =	{Chang, Yu-Sheng and Fuchs, Michael and Yu, Guan-Ru},
  title =	{{Galled Tree-Child Networks}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.8},
  URN =		{urn:nbn:de:0030-drops-204439},
  doi =		{10.4230/LIPIcs.AofA.2024.8},
  annote =	{Keywords: Phylogenetic Network, galled Network, tree-child Network, asymptotic Enumeration, Limit Law, Lagrange Inversion}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.9
On Fluctuations of Complexity Measures for the FIND Algorithm

Authors: Jasper Ischebeck and Ralph Neininger

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
The FIND algorithm (also called Quickselect) is a fundamental algorithm to select ranks or quantiles within a set of data. It was shown by Grübel and Rösler that the number of key comparisons required by FIND as a process of the quantiles α ∈ [0,1] in a natural probabilistic model converges after normalization in distribution within the càdlàg space D[0,1] endowed with the Skorokhod metric. We show that the process of the residuals in the latter convergence after normalization converges in distribution to a mixture of Gaussian processes in D[0,1] and identify the limit’s conditional covariance functions. A similar result holds for the related algorithm QuickVal. Our method extends to other cost measures such as the number of swaps (key exchanges) required by FIND or cost measures which are based on key comparisons but take into account that the cost of a comparison between two keys may depend on their values, an example being the number of bit comparisons needed to compare keys given by their bit expansions.
Cite as

Jasper Ischebeck and Ralph Neininger. On Fluctuations of Complexity Measures for the FIND Algorithm. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ischebeck_et_al:LIPIcs.AofA.2024.9,
  author =	{Ischebeck, Jasper and Neininger, Ralph},
  title =	{{On Fluctuations of Complexity Measures for the FIND Algorithm}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.9},
  URN =		{urn:nbn:de:0030-drops-204440},
  doi =		{10.4230/LIPIcs.AofA.2024.9},
  annote =	{Keywords: FIND, Quickselect, rank selection, probabilistic analysis of algorithms, weak convergence, functional limit theorem}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.10
A Bijection for the Evolution of B-Trees

Authors: Fabian Burghart and Stephan Wagner

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
A B-tree is a type of search tree where every node (except possibly for the root) contains between m and 2m keys for some positive integer m, and all leaves have the same distance to the root. We study sequences of B-trees that can arise from successively inserting keys, and in particular present a bijection between such sequences (which we call histories) and a special type of increasing trees. We describe the set of permutations for the keys that belong to a given history, and also show how to use this bijection to analyse statistics associated with B-trees.
Cite as

Fabian Burghart and Stephan Wagner. A Bijection for the Evolution of B-Trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{burghart_et_al:LIPIcs.AofA.2024.10,
  author =	{Burghart, Fabian and Wagner, Stephan},
  title =	{{A Bijection for the Evolution of B-Trees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.10},
  URN =		{urn:nbn:de:0030-drops-204451},
  doi =		{10.4230/LIPIcs.AofA.2024.10},
  annote =	{Keywords: B-trees, histories, increasing trees, bijection, asymptotic enumeration, tree statistics}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.11
Tree Walks and the Spectrum of Random Graphs

Authors: Eva-Maria Hainzl and Élie de Panafieu

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
It is a classic result in spectral theory that the limit distribution of the spectral measure of random graphs G(n,p) converges to the semicircle law in case np tends to infinity with n. The spectral measure for random graphs G(n,c/n) however is less understood. In this work, we combine and extend two combinatorial approaches by Bauer and Golinelli (2001) and Enriquez and Menard (2016) and approximate the moments of the spectral measure by counting walks that span trees.
Cite as

Eva-Maria Hainzl and Élie de Panafieu. Tree Walks and the Spectrum of Random Graphs. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hainzl_et_al:LIPIcs.AofA.2024.11,
  author =	{Hainzl, Eva-Maria and de Panafieu, \'{E}lie},
  title =	{{Tree Walks and the Spectrum of Random Graphs}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.11},
  URN =		{urn:nbn:de:0030-drops-204466},
  doi =		{10.4230/LIPIcs.AofA.2024.11},
  annote =	{Keywords: Spectrum of random matrices, generating functions}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.12
Asymptotics of Weighted Reflectable Walks in A₂

Authors: Torin Greenwood and Samuel Simon

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
Lattice walks are used to model various physical phenomena. In particular, walks within Weyl chambers connect directly to representation theory via the Littelmann path model. We derive asymptotics for centrally weighted lattice walks within the Weyl chamber corresponding to A₂ by using tools from analytic combinatorics in several variables (ACSV). We find universality classes depending on the weights of the walks, in line with prior results on the weighted Gouyou-Beauchamps model. Along the way, we identify a type of singularity within a multivariate rational generating function that is not yet covered by the theory of ACSV. We conjecture asymptotics for this type of singularity.
Cite as

Torin Greenwood and Samuel Simon. Asymptotics of Weighted Reflectable Walks in A₂. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{greenwood_et_al:LIPIcs.AofA.2024.12,
  author =	{Greenwood, Torin and Simon, Samuel},
  title =	{{Asymptotics of Weighted Reflectable Walks in A₂}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.12},
  URN =		{urn:nbn:de:0030-drops-204472},
  doi =		{10.4230/LIPIcs.AofA.2024.12},
  annote =	{Keywords: Lattice walks, Weyl chambers, asymptotics weights, analytic combinatorics in several variables}
}
  • Refine by Author
  • 9 Wild, Sebastian
  • 5 Wagner, Stephan
  • 4 Munro, J. Ian
  • 3 Janson, Svante
  • 2 Beohar, Harsh
  • Show More...

  • Refine by Classification
  • 12 Mathematics of computing → Enumeration
  • 9 Mathematics of computing → Generating functions
  • 5 Theory of computation → Random walks and Markov chains
  • 4 Theory of computation → Sorting and searching
  • 3 Mathematics of computing
  • Show More...

  • Refine by Keyword
  • 3 enumeration
  • 3 generating functions
  • 2 Multiple selection
  • 2 analysis of algorithms
  • 2 asymptotics
  • Show More...

  • Refine by Type
  • 48 document
  • 1 volume

  • Refine by Publication Year
  • 40 2024
  • 4 2023
  • 2 2018
  • 1 2020
  • 1 2021
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact