8 Search Results for "Noy, Marc"

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.SEA.2024.23
Engineering A* Search for the Flip Distance of Plane Triangulations

Authors: Philip Mayer and Petra Mutzel

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
The flip distance for two triangulations of a point set is defined as the smallest number of edge flips needed to transform one triangulation into another, where an edge flip is the act of replacing an edge of a triangulation by a different edge such that the result remains a triangulation. We adapt and engineer a sophisticated A* search algorithm acting on the so-called flip graph. In particular, we prove that previously proposed lower bounds for the flip distance form consistent heuristics for A* and show that they can be computed efficiently using dynamic algorithms. As an alternative approach, we present an integer linear program (ILP) for the flip distance problem. We experimentally evaluate our approaches on a new real-world benchmark data set based on an application in geodesy, namely sea surface reconstruction. Our evaluation reveals that A* search consistently outperforms our ILP formulation as well as a naive baseline, which is bidirectional breadth-first search. In particular, the runtime of our approach improves upon the baseline by more than two orders of magnitude. Furthermore, our A* search successfully solves most of the considered sea surface instances with up to 41 points. This is a substantial improvement compared to the baseline, which struggles with subsets of the real-world data of size 25. Lastly, to allow the consideration of global sea level data, we developed a decomposition-based heuristic for the flip distance. In our experiments it yields optimal flip distance values for most of the considered sea level data and it can be applied to large data sets due to its fast runtime.
Cite as

Philip Mayer and Petra Mutzel. Engineering A* Search for the Flip Distance of Plane Triangulations. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mayer_et_al:LIPIcs.SEA.2024.23,
  author =	{Mayer, Philip and Mutzel, Petra},
  title =	{{Engineering A* Search for the Flip Distance of Plane Triangulations}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.23},
  URN =		{urn:nbn:de:0030-drops-203887},
  doi =		{10.4230/LIPIcs.SEA.2024.23},
  annote =	{Keywords: Computational Geometry, Triangulations, Flip Distance, A-star Search, Integer Linear Programming}
}
Document
Survey
DOI: 10.4230/TGDK.2.1.3
Semantic Web: Past, Present, and Future

Authors: Ansgar Scherp, Gerd Groener, Petr Škoda, Katja Hose, and Maria-Esther Vidal

Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1

Abstract
Ever since the vision was formulated, the Semantic Web has inspired many generations of innovations. Semantic technologies have been used to share vast amounts of information on the Web, enhance them with semantics to give them meaning, and enable inference and reasoning on them. Throughout the years, semantic technologies, and in particular knowledge graphs, have been used in search engines, data integration, enterprise settings, and machine learning. In this paper, we recap the classical concepts and foundations of the Semantic Web as well as modern and recent concepts and applications, building upon these foundations. The classical topics we cover include knowledge representation, creating and validating knowledge on the Web, reasoning and linking, and distributed querying. We enhance this classical view of the so-called "Semantic Web Layer Cake" with an update of recent concepts that include provenance, security and trust, as well as a discussion of practical impacts from industry-led contributions. We conclude with an outlook on the future directions of the Semantic Web. This is a living document. If you like to contribute, please contact the first author and visit: https://github.com/ascherp/semantic-web-primer
Cite as

Ansgar Scherp, Gerd Groener, Petr Škoda, Katja Hose, and Maria-Esther Vidal. Semantic Web: Past, Present, and Future. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 3:1-3:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{scherp_et_al:TGDK.2.1.3,
  author =	{Scherp, Ansgar and Groener, Gerd and \v{S}koda, Petr and Hose, Katja and Vidal, Maria-Esther},
  title =	{{Semantic Web: Past, Present, and Future}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:37},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.3},
  URN =		{urn:nbn:de:0030-drops-198607},
  doi =		{10.4230/TGDK.2.1.3},
  annote =	{Keywords: Linked Open Data, Semantic Web Graphs, Knowledge Graphs}
}
Document
Position
DOI: 10.4230/TGDK.2.1.5
Standardizing Knowledge Engineering Practices with a Reference Architecture

Authors: Bradley P. Allen and Filip Ilievski

Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1

Abstract
Knowledge engineering is the process of creating and maintaining knowledge-producing systems. Throughout the history of computer science and AI, knowledge engineering workflows have been widely used given the importance of high-quality knowledge for reliable intelligent agents. Meanwhile, the scope of knowledge engineering, as apparent from its target tasks and use cases, has been shifting, together with its paradigms such as expert systems, semantic web, and language modeling. The intended use cases and supported user requirements between these paradigms have not been analyzed globally, as new paradigms often satisfy prior pain points while possibly introducing new ones. The recent abstraction of systemic patterns into a boxology provides an opening for aligning the requirements and use cases of knowledge engineering with the systems, components, and software that can satisfy them best, however, this direction has not been explored to date. This paper proposes a vision of harmonizing the best practices in the field of knowledge engineering by leveraging the software engineering methodology of creating reference architectures. We describe how a reference architecture can be iteratively designed and implemented to associate user needs with recurring systemic patterns, building on top of existing knowledge engineering workflows and boxologies. We provide a six-step roadmap that can enable the development of such an architecture, consisting of scope definition, selection of information sources, architectural analysis, synthesis of an architecture based on the information source analysis, evaluation through instantiation, and, ultimately, instantiation into a concrete software architecture. We provide an initial design and outcome of the definition of architectural scope, selection of information sources, and analysis. As the remaining steps of design, evaluation, and instantiation of the architecture are largely use-case specific, we provide a detailed description of their procedures and point to relevant examples. We expect that following through on this vision will lead to well-grounded reference architectures for knowledge engineering, will advance the ongoing initiatives of organizing the neurosymbolic knowledge engineering space, and will build new links to the software architectures and data science communities.
Cite as

Bradley P. Allen and Filip Ilievski. Standardizing Knowledge Engineering Practices with a Reference Architecture. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{allen_et_al:TGDK.2.1.5,
  author =	{Allen, Bradley P. and Ilievski, Filip},
  title =	{{Standardizing Knowledge Engineering Practices with a Reference Architecture}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{5:1--5:23},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.5},
  URN =		{urn:nbn:de:0030-drops-198623},
  doi =		{10.4230/TGDK.2.1.5},
  annote =	{Keywords: knowledge engineering, knowledge graphs, quality attributes, software architectures, sociotechnical systems}
}
Document
DOI: 10.4230/DagRep.12.2.1
Logic and Random Discrete Structures (Dagstuhl Seminar 22061)

Authors: Erich Grädel, Phokion G. Kolaitis, Marc Noy, and Matthias Naaf

Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22061 "Logic and Random Discrete Structures". The main topic of this seminar has been the analysis of large random discrete structures, such as trees, graphs, or permutations, from the perspective of mathematical logic. It has brought together both experts and junior researchers from a number of different areas where logic and random structures play a role, with the goal to establish new connections between such areas and to encourage interactions between foundational research and different application areas, including probabilistic databases.
Cite as

Erich Grädel, Phokion G. Kolaitis, Marc Noy, and Matthias Naaf. Logic and Random Discrete Structures (Dagstuhl Seminar 22061). In Dagstuhl Reports, Volume 12, Issue 2, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{gradel_et_al:DagRep.12.2.1,
  author =	{Gr\"{a}del, Erich and Kolaitis, Phokion G. and Noy, Marc and Naaf, Matthias},
  title =	{{Logic and Random Discrete Structures (Dagstuhl Seminar 22061)}},
  pages =	{1--16},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{2},
  editor =	{Gr\"{a}del, Erich and Kolaitis, Phokion G. and Noy, Marc and Naaf, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.2.1},
  URN =		{urn:nbn:de:0030-drops-169295},
  doi =		{10.4230/DagRep.12.2.1},
  annote =	{Keywords: combinatorics, complexity theory, logic, random structures, probabilistic databases}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.10
Cut Vertices in Random Planar Maps

Authors: Michael Drmota, Marc Noy, and Benedikt Stufler

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
The main goal of this paper is to determine the asymptotic behavior of the number X_n of cut-vertices in random planar maps with n edges. It is shown that X_n/n → c in probability (for some explicit c>0). For so-called subcritial subclasses of planar maps like outerplanar maps we obtain a central limit theorem, too.
Cite as

Michael Drmota, Marc Noy, and Benedikt Stufler. Cut Vertices in Random Planar Maps. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2020.10,
  author =	{Drmota, Michael and Noy, Marc and Stufler, Benedikt},
  title =	{{Cut Vertices in Random Planar Maps}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.10},
  URN =		{urn:nbn:de:0030-drops-120403},
  doi =		{10.4230/LIPIcs.AofA.2020.10},
  annote =	{Keywords: random planar maps, cut vertices, generating functions, local graph limits}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.116
On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface

Authors: Albert Atserias, Stephan Kreutzer, and Marc Noy

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We show that for no surface except for the plane does monadic second-order logic (MSO) have a zero-one-law - and not even a convergence law - on the class of (connected) graphs embeddable on the surface. In addition we show that every rational in [0,1] is the limiting probability of some MSO formula. This strongly refutes a conjecture by Heinig et al. (2014) who proved a convergence law for planar graphs, and a zero-one law for connected planar graphs, and also identified the so-called gaps of [0,1]: the subintervals that are not limiting probabilities of any MSO formula. The proof relies on a combination of methods from structural graph theory, especially large face-width embeddings of graphs on surfaces, analytic combinatorics, and finite model theory, and several parts of the proof may be of independent interest. In particular, we identify precisely the properties that make the zero-one law work on planar graphs but fail for every other surface.
Cite as

Albert Atserias, Stephan Kreutzer, and Marc Noy. On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 116:1-116:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{atserias_et_al:LIPIcs.ICALP.2018.116,
  author =	{Atserias, Albert and Kreutzer, Stephan and Noy, Marc},
  title =	{{On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{116:1--116:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.116},
  URN =		{urn:nbn:de:0030-drops-91206},
  doi =		{10.4230/LIPIcs.ICALP.2018.116},
  annote =	{Keywords: topological graph theory, monadic second-order logic, random graphs, zero-one law, convergence law}
}
  • Refine by Author
  • 3 Noy, Marc
  • 1 Albenque, Marie
  • 1 Allen, Bradley P.
  • 1 Atserias, Albert
  • 1 Banderier, Cyril
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Enumeration
  • 2 Computing methodologies → Knowledge representation and reasoning
  • 2 Mathematics of computing → Generating functions
  • 1 Computing methodologies → Ontology engineering
  • 1 Information systems → Markup languages
  • Show More...

  • Refine by Keyword
  • 2 generating functions
  • 1 A-star Search
  • 1 Asymptotic Enumeration
  • 1 Boltzmann distribution
  • 1 Composition schemes
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 5 2024
  • 1 2018
  • 1 2020
  • 1 2022

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