12 Search Results for "Law, Mark"


Document
Fragmentation Processes Derived from Conditioned Stable Galton-Watson Trees

Authors: Gabriel Berzunza Ojeda and Cecilia Holmgren

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)


Abstract
We study the fragmentation process obtained by deleting randomly chosen edges from a critical Galton-Watson tree 𝐭_n conditioned on having n vertices, whose offspring distribution belongs to the domain of attraction of a stable law of index α ∈ (1,2]. This fragmentation process is analogous to that introduced in the works of Aldous, Evans and Pitman (1998), who considered the case of Cayley trees. Our main result establishes that, after rescaling, the fragmentation process of 𝐭_n converges as n → ∞ to the fragmentation process obtained by cutting-down proportional to the length on the skeleton of an α-stable Lévy tree of index α ∈ (1,2]. We further establish that the latter can be constructed by considering the partitions of the unit interval induced by the normalized α-stable Lévy excursion with a deterministic drift studied by Miermont (2001). In particular, this extends the result of Bertoin (2000) on the fragmentation process of the Brownian CRT.

Cite as

Gabriel Berzunza Ojeda and Cecilia Holmgren. Fragmentation Processes Derived from Conditioned Stable Galton-Watson Trees. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{berzunzaojeda_et_al:LIPIcs.AofA.2022.3,
  author =	{Berzunza Ojeda, Gabriel and Holmgren, Cecilia},
  title =	{{Fragmentation Processes Derived from Conditioned Stable Galton-Watson Trees}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.3},
  URN =		{urn:nbn:de:0030-drops-160898},
  doi =		{10.4230/LIPIcs.AofA.2022.3},
  annote =	{Keywords: Additive coalescent, fragmentation, Galton-Watson trees, spectrally positive stable L\'{e}vy processes, stable L\'{e}vy tree, Prim’s algorithm}
}
Document
Enumeration of d-Combining Tree-Child Networks

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

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)


Abstract
Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for bicombining tree-child networks which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to d-combining tree-child networks where every reticulation node has now d ≥ 2 parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves.

Cite as

Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Michael Wallner, and Guan-Ru Yu. Enumeration of d-Combining Tree-Child Networks. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.AofA.2022.5,
  author =	{Chang, Yu-Sheng and Fuchs, Michael and Liu, Hexuan and Wallner, Michael and Yu, Guan-Ru},
  title =	{{Enumeration of d-Combining Tree-Child Networks}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.5},
  URN =		{urn:nbn:de:0030-drops-160914},
  doi =		{10.4230/LIPIcs.AofA.2022.5},
  annote =	{Keywords: Phylogenetic network, tree-child network, d-combining tree-child network, exact enumeration, asymptotic enumeration, reticulation node, limit law, stretched exponential}
}
Document
Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps

Authors: Guillaume Chapuy, Baptiste Louf, and Harriet Walsh

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)


Abstract
We study the asymptotic behaviour of random integer partitions under a new probability law that we introduce, the Plancherel-Hurwitz measure. This distribution, which has a natural definition in terms of Young tableaux, is a deformation of the classical Plancherel measure. It appears naturally in the enumeration of Hurwitz maps, or equivalently transposition factorisations in symmetric groups. We study a regime in which the number of factors in the underlying factorisations grows linearly with the order of the group, and the corresponding maps are of high genus. We prove that the limiting behaviour exhibits a new, twofold, phenomenon: the first part becomes very large, while the rest of the partition has the standard Vershik-Kerov-Logan-Shepp limit shape. As a consequence, we obtain asymptotic estimates for unconnected Hurwitz numbers with linear Euler characteristic, which we use to study random Hurwitz maps in this regime. This result can also be interpreted as the return probability of the transposition random walk on the symmetric group after linearly many steps.

Cite as

Guillaume Chapuy, Baptiste Louf, and Harriet Walsh. Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chapuy_et_al:LIPIcs.AofA.2022.6,
  author =	{Chapuy, Guillaume and Louf, Baptiste and Walsh, Harriet},
  title =	{{Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.6},
  URN =		{urn:nbn:de:0030-drops-160921},
  doi =		{10.4230/LIPIcs.AofA.2022.6},
  annote =	{Keywords: Random partitions, limit shapes, transposition factorisations, map enumeration, Hurwitz numbers, RSK algorithm, giant components}
}
Document
Census TopDown: The Impacts of Differential Privacy on Redistricting

Authors: Aloni Cohen, Moon Duchin, JN Matthews, and Bhushan Suwal

Published in: LIPIcs, Volume 192, 2nd Symposium on Foundations of Responsible Computing (FORC 2021)


Abstract
The 2020 Decennial Census will be released with a new disclosure avoidance system in place, putting differential privacy in the spotlight for a wide range of data users. We consider several key applications of Census data in redistricting, developing tools and demonstrations for practitioners who are concerned about the impacts of this new noising algorithm called TopDown. Based on a close look at reconstructed Texas data, we find reassuring evidence that TopDown will not threaten the ability to produce districts with tolerable population balance or to detect signals of racial polarization for Voting Rights Act enforcement.

Cite as

Aloni Cohen, Moon Duchin, JN Matthews, and Bhushan Suwal. Census TopDown: The Impacts of Differential Privacy on Redistricting. In 2nd Symposium on Foundations of Responsible Computing (FORC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 192, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.FORC.2021.5,
  author =	{Cohen, Aloni and Duchin, Moon and Matthews, JN and Suwal, Bhushan},
  title =	{{Census TopDown: The Impacts of Differential Privacy on Redistricting}},
  booktitle =	{2nd Symposium on Foundations of Responsible Computing (FORC 2021)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-187-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{192},
  editor =	{Ligett, Katrina and Gupta, Swati},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2021.5},
  URN =		{urn:nbn:de:0030-drops-138736},
  doi =		{10.4230/LIPIcs.FORC.2021.5},
  annote =	{Keywords: Census, TopDown, differential privacy, redistricting, Voting Rights Act}
}
Document
Open Bar - a Brouwerian Intuitionistic Logic with a Pinch of Excluded Middle

Authors: Mark Bickford, Liron Cohen, Robert L. Constable, and Vincent Rahli

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)


Abstract
One of the differences between Brouwerian intuitionistic logic and classical logic is their treatment of time. In classical logic truth is atemporal, whereas in intuitionistic logic it is time-relative. Thus, in intuitionistic logic it is possible to acquire new knowledge as time progresses, whereas the classical Law of Excluded Middle (LEM) is essentially flattening the notion of time stating that it is possible to decide whether or not some knowledge will ever be acquired. This paper demonstrates that, nonetheless, the two approaches are not necessarily incompatible by introducing an intuitionistic type theory along with a Beth-like model for it that provide some middle ground. On one hand they incorporate a notion of progressing time and include evolving mathematical entities in the form of choice sequences, and on the other hand they are consistent with a variant of the classical LEM. Accordingly, this new type theory provides the basis for a more classically inclined Brouwerian intuitionistic type theory.

Cite as

Mark Bickford, Liron Cohen, Robert L. Constable, and Vincent Rahli. Open Bar - a Brouwerian Intuitionistic Logic with a Pinch of Excluded Middle. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bickford_et_al:LIPIcs.CSL.2021.11,
  author =	{Bickford, Mark and Cohen, Liron and Constable, Robert L. and Rahli, Vincent},
  title =	{{Open Bar - a Brouwerian Intuitionistic Logic with a Pinch of Excluded Middle}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.11},
  URN =		{urn:nbn:de:0030-drops-134455},
  doi =		{10.4230/LIPIcs.CSL.2021.11},
  annote =	{Keywords: Intuitionism, Extensional type theory, Constructive Type Theory, Realizability, Choice sequences, Classical Logic, Law of Excluded Middle, Theorem proving, Coq}
}
Document
Learning Commonsense Knowledge Through Interactive Dialogue

Authors: Benjamin Wu, Alessandra Russo, Mark Law, and Katsumi Inoue

Published in: OASIcs, Volume 64, Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)


Abstract
One of the most difficult problems in Artificial Intelligence is related to acquiring commonsense knowledge - to create a collection of facts and information that an ordinary person should know. In this work, we present a system that, from a limited background knowledge, is able to learn to form simple concepts through interactive dialogue with a user. We approach the problem using a syntactic parser, along with a mechanism to check for synonymy, to translate sentences into logical formulas represented in Event Calculus using Answer Set Programming (ASP). Reasoning and learning tasks are then automatically generated for the translated text, with learning being initiated through question and answering. The system is capable of learning with no contextual knowledge prior to the dialogue. The system has been evaluated on stories inspired by the Facebook's bAbI's question-answering tasks, and through appropriate question and answering is able to respond accurately to these dialogues.

Cite as

Benjamin Wu, Alessandra Russo, Mark Law, and Katsumi Inoue. Learning Commonsense Knowledge Through Interactive Dialogue. In Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018). Open Access Series in Informatics (OASIcs), Volume 64, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{wu_et_al:OASIcs.ICLP.2018.12,
  author =	{Wu, Benjamin and Russo, Alessandra and Law, Mark and Inoue, Katsumi},
  title =	{{Learning Commonsense Knowledge Through Interactive Dialogue}},
  booktitle =	{Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)},
  pages =	{12:1--12:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-090-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{64},
  editor =	{Dal Palu', Alessandro and Tarau, Paul and Saeedloei, Neda and Fodor, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2018.12},
  URN =		{urn:nbn:de:0030-drops-98780},
  doi =		{10.4230/OASIcs.ICLP.2018.12},
  annote =	{Keywords: Commonsense Reasoning, Answer Set Programming, Event Calculus, Inductive Logic Programming}
}
Document
Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem

Authors: Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
In a companion article dedicated to the enumeration aspects, we showed how to obtain closed form formulas for the generating functions of walks, bridges, meanders, and excursions avoiding any fixed word (a pattern p). The autocorrelation polynomial of this forbidden pattern p (as introduced by Guibas and Odlyzko in 1981, in the context of regular expressions) plays a crucial role. In this article, we get the asymptotics of these walks. We also introduce a trivariate generating function (length, final altitude, number of occurrences of p), for which we derive a closed form. We prove that the number of occurrences of p is normally distributed: This is what Flajolet and Sedgewick call an instance of Borges's theorem. We thus extend and refine the study by Banderier and Flajolet in 2002 on lattice paths, and we unify several dozens of articles which investigated patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. Our approach relies on methods of analytic combinatorics, and on a matricial generalization of the kernel method. The situation is much more involved than in the Banderier-Flajolet work: forbidden patterns lead to a wider zoology of asymptotic behaviours, and we classify them according to the geometry of a Newton polygon associated with these constrained walks, and we analyse what are the universal phenomena common to all these models of lattice paths avoiding a pattern.

Cite as

Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger. Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{asinowski_et_al:LIPIcs.AofA.2018.10,
  author =	{Asinowski, Andrei and Bacher, Axel and Banderier, Cyril and Gittenberger, Bernhard},
  title =	{{Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.10},
  URN =		{urn:nbn:de:0030-drops-89035},
  doi =		{10.4230/LIPIcs.AofA.2018.10},
  annote =	{Keywords: Lattice paths, pattern avoidance, finite automata, context-free languages, autocorrelation, generating function, kernel method, asymptotic analysis, Gaussian limit law}
}
Document
Periodic Pólya Urns and an Application to Young Tableaux

Authors: Cyril Banderier, Philippe Marchal, and Michael Wallner

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
Pólya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial non-linear partial differential equation indeed leads to linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.

Cite as

Cyril Banderier, Philippe Marchal, and Michael Wallner. Periodic Pólya Urns and an Application to Young Tableaux. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2018.11,
  author =	{Banderier, Cyril and Marchal, Philippe and Wallner, Michael},
  title =	{{Periodic P\'{o}lya Urns and an Application to Young Tableaux}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.11},
  URN =		{urn:nbn:de:0030-drops-89045},
  doi =		{10.4230/LIPIcs.AofA.2018.11},
  annote =	{Keywords: P\'{o}lya urn, Young tableau, generating functions, analytic combinatorics, pumping moment, D-finite function, hypergeometric function, generalized Gamma distribution, Mittag-Leffler distribution}
}
Document
Asymptotic Distribution of Parameters in Random Maps

Authors: Olivier Bodini, Julien Courtiel, Sergey Dovgal, and Hsien-Kuei Hwang

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We consider random rooted maps without regard to their genus, with fixed large number of edges, and address the problem of limiting distributions for six different parameters: vertices, leaves, loops, root edges, root isthmus, and root vertex degree. Each of these leads to a different limiting distribution, varying from (discrete) geometric and Poisson distributions to different continuous ones: Beta, normal, uniform, and an unusual distribution whose moments are characterised by a recursive triangular array.

Cite as

Olivier Bodini, Julien Courtiel, Sergey Dovgal, and Hsien-Kuei Hwang. Asymptotic Distribution of Parameters in Random Maps. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{bodini_et_al:LIPIcs.AofA.2018.13,
  author =	{Bodini, Olivier and Courtiel, Julien and Dovgal, Sergey and Hwang, Hsien-Kuei},
  title =	{{Asymptotic Distribution of Parameters in Random Maps}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.13},
  URN =		{urn:nbn:de:0030-drops-89069},
  doi =		{10.4230/LIPIcs.AofA.2018.13},
  annote =	{Keywords: Random maps, Analytic combinatorics, Rooted Maps, Beta law, Limit laws, Patterns, Generating functions, Riccati equation}
}
Document
Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes

Authors: Michael Drmota, Lander Ramos, Clément Requilé, and Juanjo Rué

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in series-parallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law.

Cite as

Michael Drmota, Lander Ramos, Clément Requilé, and Juanjo Rué. Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2018.18,
  author =	{Drmota, Michael and Ramos, Lander and Requil\'{e}, Cl\'{e}ment and Ru\'{e}, Juanjo},
  title =	{{Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.18},
  URN =		{urn:nbn:de:0030-drops-89117},
  doi =		{10.4230/LIPIcs.AofA.2018.18},
  annote =	{Keywords: Asymptotic enumeration, central limit laws, subcritical graph classes, maximal independent set, maximal matching}
}
Document
Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex

Authors: Benedikt Stufler

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We prove limit theorems describing the asymptotic behaviour of a typical vertex in random simply generated trees as their sizes tends to infinity. In the standard case of a critical Galton-Watson tree conditioned to be large, the limit is the invariant random sin-tree constructed by Aldous (1991). Our main contribution lies in the condensation regime where vertices of macroscopic degree appear. Here we describe in complete generality the asymptotic local behaviour from a random vertex up to its first ancestor with "large" degree. Beyond this distinguished ancestor, different behaviours may occur, depending on the branching weights. In a subregime of complete condensation, we obtain convergence toward a novel limit tree, that describes the asymptotic shape of the vicinity of the full path from a random vertex to the root vertex. This includes the important case where the offspring distribution follows a power law up to a factor that varies slowly at infinity.

Cite as

Benedikt Stufler. Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 34:1-34:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{stufler:LIPIcs.AofA.2018.34,
  author =	{Stufler, Benedikt},
  title =	{{Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{34:1--34:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.34},
  URN =		{urn:nbn:de:0030-drops-89276},
  doi =		{10.4230/LIPIcs.AofA.2018.34},
  annote =	{Keywords: Galton-Watson trees, local weak limits}
}
Document
The Elements of Decision Alignment

Authors: Mark S. Miller and Bill Tulloh

Published in: LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)


Abstract
When one object makes a request of another, why do we expect that the second object's behavior correctly satisfies the first object's wishes? The need to cope with such principal-agent problems shapes programming practice as much as it shapes human organizations and economies. However, the literature about such plan coordination issues among humans is almost disjoint from the literature about these issues among objects. Even the terms used are unrelated. These fields have much to learn from each other---both from their similarities and from the causes of their differences. We propose a framework for thinking about decision alignment as a bridge between these disciplines.

Cite as

Mark S. Miller and Bill Tulloh. The Elements of Decision Alignment. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 17:1-17:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{miller_et_al:LIPIcs.ECOOP.2016.17,
  author =	{Miller, Mark S. and Tulloh, Bill},
  title =	{{The Elements of Decision Alignment}},
  booktitle =	{30th European Conference on Object-Oriented Programming (ECOOP 2016)},
  pages =	{17:1--17:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-014-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{56},
  editor =	{Krishnamurthi, Shriram and Lerner, Benjamin S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.17},
  URN =		{urn:nbn:de:0030-drops-61111},
  doi =		{10.4230/LIPIcs.ECOOP.2016.17},
  annote =	{Keywords: economics, law, contracts, principal-agent problem, incentive alignment, least authority, verification}
}
  • Refine by Author
  • 2 Banderier, Cyril
  • 2 Wallner, Michael
  • 1 Asinowski, Andrei
  • 1 Bacher, Axel
  • 1 Berzunza Ojeda, Gabriel
  • Show More...

  • Refine by Classification
  • 4 Mathematics of computing → Enumeration
  • 3 Mathematics of computing → Distribution functions
  • 3 Mathematics of computing → Generating functions
  • 2 Mathematics of computing → Random graphs
  • 2 Theory of computation → Random walks and Markov chains
  • Show More...

  • Refine by Keyword
  • 2 Galton-Watson trees
  • 1 Additive coalescent
  • 1 Analytic combinatorics
  • 1 Answer Set Programming
  • 1 Asymptotic enumeration
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 6 2018
  • 3 2022
  • 2 2021
  • 1 2016

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