https://www.dagstuhl.de/20451

November 1 – 6 , 2020, Dagstuhl Seminar 20451

Logic and Random Discrete Structures

Organizers

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)

For support, please contact

Susanne Bach-Bernhard for administrative matters

Michael Gerke for scientific matters

Documents

Dagstuhl Seminar Schedule (Upload here)

(Use personal credentials as created in DOOR to log in)

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

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.