https://www.dagstuhl.de/20451

01. – 06. November 2020, Dagstuhl-Seminar 20451

Logic and Random Discrete Structures

Organisatoren

Erich Grädel (RWTH Aachen, DE)
Phokion G. Kolaitis (University of California – Santa Cruz & IBM Almaden Research Center – San Jose, US)
Tobias Müller (University of Groningen, NL)
Marc Noy (UPC Barcelona Tech, ES)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Susanne Bach-Bernhard zu administrativen Fragen

Michael Gerke zu wissenschaftlichen Fragen

Dokumente

Teilnehmerliste
Gemeinsame Dokumente
Dagstuhl-Seminar Wiki
Programm des Dagstuhl-Seminars (Hochladen)

(Zum Einloggen bitte persönliche DOOR-Zugangsdaten verwenden)

Motivation

The analysis of large random discrete structures, such as trees, graphs, or permutations, is a main research focus in contemporary discrete mathematics. The overall goal is to understand the “typical structure'' of objects from a given class by studying the behavior of a randomly chosen object from that class. Logic provides a useful and powerful formalism for classifying discrete structures and for expressing properties of discrete structures; for this reason, the lens of logic has also been used in the study of random discrete structures.

The connections between logic and random discrete structure trace their origin to the discovery of the zero-one law for first-order logic on finite structures under the uniform probability measure, a celebrated result due to Glebskii et al. and, independently, to Fagin. Since the discovery of this result five decades ago, logical limit laws or convergence laws have been established for several different models of random discrete structures and for various logics, including fragments of second-order logic and extensions of first-order logic with fixed-point constructs. Furthermore, fundamental algorithmic problems associated with the computation of asymptotic probabilities have been explored.

In recent years, connections between logic and random discrete structures have emerged in different frameworks that span a broad spectrum of areas, from extremal combinatorics to modeling uncertainty in data, and typically use distinct techniques. For example, the frameworks of graph limits and flag algebras are concerned with the study of asymptotic densities of structures, while the framework of probabilistic databases is concerned with the study of queries posed against inherently uncertain data. Logic has been successfully used in all these frameworks to provide a coherent viewpoint and to contribute to the establishment of unifying results.

The main aim of this Dagstuhl Seminar is to bring together researchers, both junior and senior, from different areas, such as logic, combinatorics, data uncertainty, and randomized algorithms, to share state-of-the-art advances in the interaction between these areas, present overviews of methods and techniques based on the combination of logic and discrete random structures, discuss open problems, and shape future directions of research in these fields.

Motivation text license
  Creative Commons BY 3.0 DE
  Erich Grädel, Phokion G. Kolaitis, Tobias Müller, and Marc Noy

Classification

  • Data Structures / Algorithms / Complexity
  • Verification / Logic

Keywords

  • Logic. Model theory. Random Graphs. Combinatorics. Complexity theory

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.