THEMATIC MONTH - MOIS THÉMATIQUE
Discrete Mathematics & Computer Science: Groups, Dynamics, Complexity, Words
Mathématiques discrètes et informatique : mots, complexité, dynamique, groupes
29 January – 02 Mars, 2024
Julien Cassaigne (CNRS, Aix-Marseille Université)
Jérémie Chalopin (CNRS, Aix-Marseille Université)
Victor Chepoi (Aix-Marseille Université)
Anna Frid (Aix-Marseille Université)
Pierre Guillon (CNRS, Aix-Marseille Université)
Étienne Moutot (CNRS, Aix-Marseille Université)
Nicolas Ollinger (Université d’Orléans)
Andrei Romashchenko (CNRS, Université de Montpellier)
Guillaume Theyssier (CNRS, Aix-Marseille Université)
Pascal Vanier (Université de Caen Normandie)
The interface of mathematics with computer science form a large, diverse and rich landscape. Of course, many classical mathematical tools and concepts turn out to be very useful to answer questions arising from computer science. Besides, the core objects of computer science (typically discrete) that were once considered non-classical in mathematics have now a well-established and growing theory. In addition, the main ideas of computer science (the very notions of computation and algorithmic complexity) yield new points of views and new questions on many mathematical objects.
This thematic month proposes a walk along discrete mathematics and computation theory to explore both a range of mathematical objects (groups, symbolic dynamical systems, words, . . . ) and a range of notions from computer science (information, randomness, computability, complexity,. . . ) that share many strong links. To encourage participants (especially the youngest ones) to attend the entire month and foster interactions outside each one’s expertise zone, the first week will consist in a research school with in-depth introduction to the key objects and notions of the entire month.
The month is then organized around four scientific pillars that will be the focus of four successive weeks:
• Geometric and Asymptotic Group Theory with Applications (GAGTA 2024), on week 2, will be devoted to infinite groups, as they offer a meeting point of many fields: algebra, geometry, dynamical systems, graph theory and computability theory.
• Complexity of Simple Dynamical Systems, on week 3, will be devoted to the interplay between dynamical systems theory and computability or complexity theory.
• Randomness, Information & Complexity, on week 4, will study various connections between information and computation theory, ranging from communication complexity, information complexity and Kol- mogorov complexity, to pseud-random structures and computability.
• Combinatorics on words, on week 5, will focus on finite and infinite words, linking discrete dynamics and number theory to computer science. One important topic will be automatic problem solving on words.
All these subjects have a lot in common, and we chose to organize them in this order to have a coherent program for the whole month, empathizing particular interactions across the successive weeks. Here are some examples of these interactions. A major trend in symbolic dynamics is to consider tilings or cellular automata over arbitrary groups, or to study the group of automorphisms of a subshift. On another point of view, a striking similarity has been discovered in the last decade between the history of computational aspects of multidimensional symbolic dynamics and of group theory. Several notions of complexity coming from computation and information theory (like communication or Kolmogorov complexity, or arithmetical hierarchy and Turing degrees) have been successfully used to analyze symbolic dynamical systems in complement to standard notions like Kolmogorov-Sinaï) entropy. The link between dynamics and combinatorics on words is clear, for example through the trace object, or symbolic complexity as a refinement for entropy. It also presents strong connexion with computation, for instance in the decidability problems for some properties of substitutions, or the links with string compression.
Research School in Discrete Mathematics and Computer Science
École de recherche en mathématiques discrètes et informatique
29 January – 02 February, 2024
SAGA, Symposium on Arithmetic Geometry and its Applications
Symposium sur la géométrie arithmétique et ses applications
6 – 10 February 2023
COGNAC, Conference On alGebraic varieties over fiNite fields and Algebraic geometry Codes
Conférence sur les variétés algébriques sur les corps finis et les codes géométriques algébriques
13 – 17 February 2023
ALCOCRYPT, ALgebraic and combinatorial methods for COding and CRYPTography
Méthodes algébriques et combinatoires pour le codage et la cryptographie
20 – 24 February 2023
COUNT, COmputations and their Uses in Number Theory
Les calculs et leurs utilisations en théorie des nombres
27 February – 3 March 2023