Invited Speakers

Olivier Bournez (LIX, École Polytechnique, Palaiseau): Computing with ordinary differential equations

Ordinary Differential Equations (ODEs) appear to be a universally adopted and very natural way for expressing properties for continuous time dynamical systems. They are intensively used, in particular in applied sciences. There exists an abundant literature about the hardness of solving ODEs with numerical methods.

We will here adopt a dual view: we consider ODEs as a way to program or to describe our mathematical/computer science world. We will survey several results considering ODEs under this computational perspective, with a computability and complexity theory point of view. In particular, we will provide various reasons why polynomial ODEs should be considered as the continuous time analog of Turing machines for continuous-time computations, or should be used as a way to talk about mathematical logic.

This has already applications in various fields: determining whether analog models of computation can compute faster than classical digital models of computation, computability; solving complexity issues for computations with biochemical reactions in bioinformatics; machine independent characterizations of various computability and complexity classes such as P or NP, or proof of the existence of a universal polynomial ordinary differential equation whose solutions can approximate any continuous function if provided with a suitable well-chosen initial condition.

Martin Grohe (RWTH Aachen University): Weisfeiler and Leman's Unlikely Journey from Graph Isomorphism to Neural Networks - TALK CANCELLED

The Weisfeiler-Leman algorithm is a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced. In the first part of my talk, I will give an introduction to the Weisfeiler-Leman algorithm and its various characterisations. In the second part I will speak about its applications, in particular about recent work relating the algorithm to graph neural networks.

Dana Randall (Georgia Institute of Technology): Statistical physics and algorithms - TALK CANCELLED

Markov chain Monte Carlo methods have become ubiquitous across science and engineering as a means of exploring large configuration spaces. Over the last 30 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose, largely building on insights from statistical physics. One of the striking discoveries has been the realization that many natural Markov chains undergo a phase transition whereby they change from being efficient to inefficient as some parameter of the system is varied. In this talk we will explore this phenomenon, and show how insights from computing and statistical physics reveal interesting results across many applications domains, including asynchronous models of programmable matter.

Dimitrios Thilikos (LIRMM, Montpellier University, CNRS): Modification Problems and their Parameterizations

A great variety of algorithmic problems on graphs can be seen as Graph Modification Problems. Each such problem is defined given a desired graph property P and a set M} of permitted types of modification operations that are typically local transformations such as vertex/edge removal, edge addition, and others. Each choice of P and M generates a problem whose input is a graph $G$ and a non-negative integer k and whose question is whether it is possible to transform G to a graph in P after the application of k modifications from M. Most problems generated under this setting are computationally hard, therefore a big part of research on graph modification problems has been oriented to the design of parameterized algorithms. In this talk we provide general classification patters for graph modification problems based either on partial relations of graphs or on logical characterizations. We also present the most relevant parameterizations of such problems and we survey a series of related algorithmic or complexity results as well as prominent open questions in this field.

Online user: 10

Privacy