TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 22061

Logic and Random Discrete Structures

( Feb 06 – Feb 11, 2022 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/22061

Organizers

Contact



Schedule

Summary

Topic and Goals of the Seminar

The analysis of large random discrete structures, such as trees, graphs, or permutations, is a focus of research in contemporary discrete mathematics. Logic provides a useful and powerful formalism for expressing and classifying discrete structures; moreover, it is intimately linked to the study of algorithms, computational complexity, and structural graph theory. Over the past several decades, researchers have studied random discrete structures from a logical perspective. The first significant result in this direction was the zero-one law for first-order logic under the uniform measure; this seminal result, was followed by the discovery of ‘logical limit laws’ or ‘convergence laws’ for several different models of random discrete structures and for various logics of significance in computer science. In more recent years, a renewed impetus has emerged for research activity on random discrete structures from a logical perspective. This is in part due to the availability of new methods and techniques, including asymptotic enumeration, discrete harmonic analysis, an extension of Gowers norms, and limit structures. Exciting new results on random geometric graphs, graphs on surfaces, classes of sparse graphs, graph limits, and flag algebras have been established. On the computer science side, there has been a systematic exploration of probabilistic databases, which has brought together databases, logic, and random structures. The main aim of this seminar has been to bring together some of the foremost experts from these different fields, as well as junior researchers who may become motivated to work deeper in the frontier of logic and random structures. In addition to making tangible progress on some of the currently outstanding open problems in this area, we wanted to establish new connections between (classical) random discrete structures, flag algebras, and sparse graph limits, both in terms of identifying new research questions and embarking on new collaborations, as well as fruitful interaction between foundational research and different application areas, including probabilistic databases.

Organisation and Activities

Despite the restrictions and problems caused by corona pandemic, the seminar had originally been intended as a non-hybrid event with all participants on site. At the end, however, this turned out to be infeasible; as a result, two of the invited survey talks and a number of the contributed talks had to be given remotely via Zoom.

The organisers created a schedule consisting of four invited one-hour survey talks, and more focussed regular contributions proposed by the participants. The survey talks were given by

  • Albert Atserias on certifying the chromatic number of a random graph;
  • Fiona Skerman on the inference of underlying community structures in partially observed graphs;
  • Dan Suciu on probabilistic databases;
  • Patrice Ossona de Mendez on limits of graphs.

The talks of Fiona Skerman and Patrice Ossona de Mendez were given over Zoom.

In addition, there were 18 contributed talks, 11 of which were given on site, and 7 remotely via Zoom.

Overall, the organisers regard the seminar to have been a very successful scientific event. There was a general view shared by all participants that the community working on logic and random structures is in excellent shape, with interesting new developments and exciting results in many different directions. The participants clearly expressed the wish to a have a future meeting of this community, be in in Dagstuhl or elsewhere, within the next two to three years.

The organisers are grateful to the Scientific Directorate and to the staff of the Center for their support of this seminar.

Copyright Erich Grädel, Phokion G. Kolaitis, and Marc Noy

Motivation

The analysis of large random discrete structures, such as trees, graphs, or permutations, is a focus of research in contemporary discrete mathematics. Logic provides a useful and powerful formalism for expressing and classifying discrete structures; moreover, it is intimately linked to the study of algorithms, computational complexity, and structural graph theory. Over the past several decades, researchers have studied random discrete structures from a logical perspective. The first significant result in this direction was the zero-one law for first-order logic under the uniform measure; this seminal result, was followed by the discovery of ‘logical limit laws’ or ‘convergence laws’ for several different models of random discrete structures and for various logics of significance in computer science.

In more recent years, a renewed impetus has emerged for research activity on random discrete structures from a logical perspective. This is in part due to the availability of new methods and techniques, including asymptotic enumeration, discrete harmonic analysis, an extension of Gowers norms, and limit structures. Exciting new results on random geometric graphs, graphs on surfaces, classes of sparse graphs, graph limits, and flag algebras have been established. On the computer science side, there has been a systematic exploration of probabilistic databases, which has brought together databases, logic, and random structures.

The main aim of this Dagstuhl Seminar is to bring together some of the foremost experts from these different fields, as well as junior researchers who may become motivated to work deeper in the frontier of logic and random structures. In addition to making tangible progress on some of the currently outstanding open problems in this area, we expect that new connections may be made between (classical) random discrete structures, flag algebras, and sparse graph limits, both in terms of identifying new research questions and embarking on new collaborations. Furthermore, we expect that there will be fruitful interaction between foundational research and different application areas, including probabilistic databases.

The seminar will feature three or four tutorials or broad overview talks on different topics, so that all participants develop a common background. In addition, there will be a few long talks and several short talks in which state-of-the-art advances will be communicated. The program will be complemented by one or two problem sessions and by a discussion assessing the seminar and planning the next steps. The schedule will provide ample time for informal interactions and collaboration between participants.

Copyright Erich Grädel, Phokion G. Kolaitis, and Marc Noy

Participants
On-site
  • Aida Abiad (TU Eindhoven, NL)
  • Isolde Adler (University of Leeds, GB) [dblp]
  • Albert Atserias (UPC Barcelona Tech, ES) [dblp]
  • Manuel Bodirsky (TU Dresden, DE) [dblp]
  • Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
  • Anuj Dawar (University of Cambridge, GB) [dblp]
  • Valentin Feray (CNRS - Vandoeuvre-lès-Nancy, FR) [dblp]
  • Erich Grädel (RWTH Aachen, DE) [dblp]
  • Benny Kimelfeld (Technion - Haifa, IL) [dblp]
  • Peter Lindner (EPFL Lausanne, CH) [dblp]
  • Tobias Müller (University of Groningen, NL) [dblp]
  • Matthias Naaf (RWTH Aachen, DE) [dblp]
  • Marc Noy (UPC Barcelona Tech, ES) [dblp]
  • Oleg Pikhurko (University of Warwick - Coventry, GB) [dblp]
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Dan Suciu (University of Washington - Seattle, US) [dblp]
  • Lidia Tendera (University of Opole, PL) [dblp]
  • Teun Verstraaten (University of Groningen, NL)
Remote:
  • Andreas R. Blass (University of Michigan - Ann Arbor, US) [dblp]
  • Valentin Goranko (University of Stockholm, SE) [dblp]
  • Batya Kenig (Technion - Haifa, IL) [dblp]
  • Lefteris M. Kirousis (University of Athens, GR) [dblp]
  • Phokion G. Kolaitis (University of California - Santa Cruz, US) [dblp]
  • Daniel Král' (Masaryk University - Brno, CZ) [dblp]
  • Jerzy Marcinkowski (University of Wroclaw, PL) [dblp]
  • Patrice Ossona de Mendez (EHESS - Paris, FR) [dblp]
  • Sudeepa Roy (Duke University - Durham, US) [dblp]
  • Fiona Skerman (Uppsala University, SE) [dblp]
  • Christoph Standke (RWTH Aachen, DE)
  • Szymon Torunczyk (University of Warsaw, PL) [dblp]
  • Maksim Zhukovskii (MIPT - Dolgoprudny, RU) [dblp]

Classification
  • Databases
  • Discrete Mathematics
  • Logic in Computer Science

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