Schedule

Lundi 25

• 9h45 - 10h45 : Bruno Durand et Grégory Lafitte : Tutoriel Admissibles (slides)
• 10h45 - 11h : Pause
• 11h - 11h45 : Benjamin Hellouin
• 12h - 13h30 : Repas
• 13h30 - 14h15 : Alexander Shen (slides)
• 14h30 - 15h15 : Quentin Guilmant
• 15h15 : Discussions

Mardi 26

• 9h45 - 10h45 : Bruno Durand et Grégory Lafitte : Tutoriel Admissibles
• 10h45 - 11h : Pause
• 11h - 11h45 :  Benoit Monin
• 12h - 13h30 : Repas
• 13h30 - 14h15 : Pascal Vanier (slides)
• 14h30 - 15h15 : Olivier Bournez (slides)
• 15h30 - 16h15 : Amaury Pouly (slides)

Mercredi 27

• 9h45 - 10h30 : Ludovic Patey (slides)
• 11h - 11h45 : Laurent Bienvenu
• 12h : Repas et fin des journées

Lundi 25

• 9h45 - 10h45 : Bruno Durand et Grégory Lafitte : Tutoriel Admissibles
• 10h45 - 11h : Pause
• 11h - 11h45 : Benjamin Hellouin :

  Le problème du domino (et ses variantes) est le problème de décidabilité originel de la théorie des pavages. Il est bien connu que ce problème est décidable sur Z et indécidable sur Z^2, et ceci est dû à l'existence d'espaces de pavage apériodiques dans ce dernier.

  L'interêt récent envers les pavages apériodiques et le problème du domino sur d'autres groupes permet de mieux comprendre les propriétés qui séparent les cas décidable et indécidable. Mon but est de faire un tour d'approche élémentaire de ces questions, et notamment la relation entre les pavages de différents groupes qui utilisent les mêmes tuiles.

  J'en profiterai pour parler d'un résultat récent (issus d'une collaboration avec Hugo Maturana Cornejo, université du Chili) sur le lien entre le problème du domino périodique "général" et le problème du domino sur les groupes moyennables.

   

• 12h - 13h30 : Repas
• 13h30 - 14h15 : Alexander Shen
  Randomness generators: theory and practice
  
  There is a mathematical definition of randomness (Martin-Lof's definition for infinite sequences, randomness as incompressibility for finite sequences). Also there are "practical" random bits generators (called "non-deterministic randomness generators", as opposed to "deterministic randomness generators", or pseudo-randomness generators). There are test suites (diehard, dieharder, NIST), NIST standards for the generators, etc. However, these two worlds are almost disjoint and we think it is instructive to look at the practical situation from a mathematical point of view. It turns out that there is a lot of questionable practices in the construction and testing of pseudo-randomness generators; we will try to describe what are these weak points. (Work performed during RaCAF project)
• 14h30 - 15h15 : Quentin Guilmant

  Approche du calcul surréel par l'intégration.

  Les nombres surréels sont des nombres introduit par Conway et Gonshor. Ils ont le très bon goût, en tant que classe, de former un corps réel clos. Il est d'ailleurs universel dans le sens ou tout corps réel clos peut être codé dans les nombres surréels. Cette propriété est certes fort sympathique mais ils ont tout de même un gros défaut. Au contraire du modèle du corps des réels, les corps de surréels contiennent des trous. Le trou le plus simple est celui qu'il y a entre les nombres finis et les nombres infiniment grand (positifs). Ces trous participent grandement à nous empêcher de donner une bonne définition de l'intégration sur ces nouveaux nombres. C'est aussi eux qui permettent aux fonctions continues de ne plus satisfaire des théorèmes élémentaires d'analyse comme le théorème des valeurs extrêmes ou de théorème des valeurs intermédiaires. Cet exposé propose d'introduire les nombres surréels, les opérations que l'on peut faire avec, les diverses représentation que l'on peut en faire, notamment d'un point de vu de l'analyse récursive, ainsi que les pistes prometteuses pour réussir à définir une intégration suffisante pour développer une théorie du calcul, notamment grâce au calcul différentiel.

• 9h45 - 10h45 : Bruno Durand et Grégory Lafitte : Tutoriel Admissibles
• 10h45 - 11h : Pause
• 11h - 11h45 :  Benoit Monin

  Lowness of the Pigeonhole principle

  Given a coloring c of the integers into two colors, there must be, by the pigeonhole principle, an infinite set X such that c assigns the same color to every element of X. This rather easy theorem is known as the RT12 principle in reverse mathematics : An instance of RT12 is a coloring c of the integers into two colors, and a solution of this instance is an infinite set X whose every element is assigned the same color via c. We study the general question of the computational power of RT12: Given a notion of "computational strength", that is, an upward closed class C in the Turing degree, can we build an instance c of RT12 such that every solution to c is a member of C? The general paradigm is that RT12 has very little computational power. For almost every known natural notion of "computational strength" C, it is known that RT12 is low for this notion : for every instance c of RT12, there is a solution of c which is not a member of C. One of the first of these result is that for any non computable set X and any instance c of RT12, one solution of c does not compute X (Dzhafarov and Jockusch). To show this, the authors designed a special forcing notion : the computable Mathias forcing, with which one can control the truth of Sigma01 statements. Later, Monin and Patey designed a new forcing notion, that builds upon computable Mathias forcing, in order to control the truth of Sigma02 statements. This lead to the following result : for every instance c of RT12, there is a solution of c which is not of high degree, that is whose jump does not compute the double jump. Later the same authors could obtain a generalization of this forcing in two ways : the first one to control the truth of Sigma0\alpha statements for alpha a computable ordinal, and the second one by "iterating" the forcing within product spaces, in order to obtain non-cohesive solutions, leading a separation of the reverse mathematical principles RT22 and SRT22.

• 13h30 - 14h15 : Pascal Vanier

  The relationship between word complexity and computational complexity in subshifts

  We prove several results about the relationship between the word complexity function of a subshift and the set of Turing degrees of points of the subshift, which we call the Turing spectrum. Among other results, we show that a Turing spectrum can be realized via a subshift of linear complexity if and only if it consists of the union of a finite set and a finite number of cones, that a Turing spectrum can be realized via a subshift of exponential complexity (i.e. positive entropy) if and only if it contains a cone, and that every Turing spectrum which either contains degree 0 or is a union of cones is realizable by subshifts with a wide range of 'intermediate' complexity growth rates between linear and exponential.

• 14h30 - 15h15 : Olivier Bournez

  Recursion schemes, discrete differential equations and characterization of polynomial time computations

  This work published in MFCS'2019 studies the expressive and computational power of discrete Ordinary Differential Equations (ODEs). It presents a new framework using discrete ODEs as a central tool for computation and algorithm design. We present the general theory of discrete ODEs for computation theory, we illustrate this with various examples of algorithms, and we provide several implicit characterizations of complexity and computability classes. The proposed framework presents an original point of view on complexity and computation classes. It unifies several constructions that have been proposed for characterizing these classes including classical approaches in implicit complexity using restricted recursion schemes, as well as recent characterizations of computability and complexity by classes of continuous ordinary differential equations. It also helps understanding the relationships between analog computations and classical discrete models of computation theory. At a more technical point of view, this paper points out the fundamental role of linear (discrete) ordinary differential equations and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming many algorithms.

• 15h30 - 16h15 : Amaury Pouly

  On the Decidability of Reachability in Linear Time-Invariant Systems

  We consider the decidability of state-to-state reachability in discrete- time linear time-invariant control systems, with control sets defined by boolean combinations of linear inequalities. It is a fundamental result in control theory that the version of this problem in which the control set is an affine subspace (i.e., definable by a conjunction of equations) is decidable in polynomial time. We show that reachability is undecidable if the control set can be a finite union of affine subspaces. We moreover show that if the control set consists of a single affine subspace together with an additional point then reachability is as hard as Skolem's Problem for linear recurrence sequences. In like manner we show that if the control set in a convex polytope then reachability is as hard as the Positivity Problem for linear recurrence sequences. Our main result shows decidability of the reachability problem for convex polytopic control sets under some spectral assumptions on the transition matrix of an LTI system.

Mercredi 27

• 9h45 - 10h30 : Ludovic Patey

  SRT22 does not imply RT22 in omega-models

  In this talk, nous présentons les underlying techniques for separating la version stable du théorème de Ramsey pour les paires de sa version non-stable. Notre motivation vient des reverse mathematics. Ce projet est un joint work avec Benoit Monin.

• 11h - 11h45 : Laurent Bienvenu

  Optimal bounds for single-source Kolmogorov extractors

  The rate of randomness (or dimension) of a binary string x is the ratio C(x)/|x| where C(x) is the Kolmogorov complexity of x. While it is known that a single computable transformation cannot increase the rate of randomness of all strings, Fortnow et al. showed that for any 0<alpha<beta<1, there are a finite number of computable transformations such that any string of rate at least alpha is turned into a string of rate at least beta by one of these transformations (ICALP 2006). However, their proof only gives very loose bounds on the correspondence between the number of transformations and the increase of rate of randomness one can achieve. Further work of Zimand (CCC 2011) gave a more precise estimate, but the exact correspondence between the number of computable transformations and the achievable rate of randomness increase remained an open question. By translating this problem to combinatorics on (hyper)graphs, we provide a tight bound, namely: Using k transformations, one can get an increase from rate alpha to any rate beta < kalpha/(1+(k-1)alpha), and this is optimal. This is joint work with Barbara Csima and Matthew Harrison-Trainor