∂IFFERENCE
Complexity theory with discrete ODEs
Théorie de la complexité avec des équations différentielles discrètes
Meetings
- December 1st 2020
- January 11 2021
- June 25 2021
- September 6 2021
- October 18 2021
- October 6 2022
- March 30 2023
- January 12 2024
Partie réservée aux membres
Outputs
Location
Shared with the annual meeting of SDA2. The third of the 3 days of the SDA2 meeting will be devoted to ANR Difference
This will happen at IMT in Amphi Laurent Schwartz.
In French Pour venir, le plus simple est de prendre le métro jusqu'à Université Paul Sabatier, le bâtiment de l'IMT est à une centaine de mètres de la station, c'est le premier bâtiment que l'on rencontre après le bâtiment d'acueil.
L'Amphi Schwartz se trouve dans le hall de l'IMT (bâtiment 1R3), si la porte pour rentrer dans le bâtiment est fermée, le code est 5162 A.
Vous pouvez trouver des informations sur:
Program
See program of March 31 of SDA2 meeting
- Daniel Graça slides
Continuous robust simulation of Turing machines on low-dimensional dynamical systems
Abstract: In this talk we will analyze the problem of finding the minimum dimension over which a discrete-time/continuous-time dynamical system defined over the real space can simulate a Turing machine. In particular, we will consider this problem for (i) simulations which are robust to perturbations (i.e. which do not break down on the presence of a small amount of "noise") and (ii) for which the dynamics is analytic (as it happens in many physically realistic systems). We show that one-dimensional analytic maps are sufficient to robustly simulate Turing machines. On the other hand, under some reasonable assumptions, the minimum dimension needed to robustly simulate Turing machines with analytic ordinary differential equations is two. We also show that any Turing machine can be simulated by a smooth two-dimensional ordinary differential equation on the compact sphere. Talk based on joint work with Ning Zhong.
Titre: Caractérisation des systèmes dynamiques "lents" sur le Cantor:
Résumé: Avec Piotr Oprocha, nous avons étudié la question de quels systèmes dynamiques sur le Cantor peuvent être vus comme un sous-système d'un système de l'intervalle dérivable de telle manière que la dérivée est nulle partout sur le Cantor (on dit qu'un tel système est lent). Il était déjà connu que tout système minimal sur le Cantor satisfait cela. La preuve utilise la représentation de Gambaudo-Martens des système minimaux sur le Cantor. Nous avons caractérisé complètement les systèmes lents comme ceux dont toutes les orbites finies sont des attracteurs. Je présenterai ce résultat et les idées derrière la preuve de ce résultat.
Pause
- Riccardo Gozzi slides
Totalization for ODEs.
We will present the work in progress on defining totalization for ODEs.
- Alonso H. Núñez slides
Lunch
- Alexey Barsukov slides
Title: Feder and Vardi’s Non-Dichotomy Theorem Revisited
Abstract: I show that every NP problem is P-time equivalent to a problem described by a Monotone Monadic SNP sentence with inequality. This theorem was first stated by Feder and Vardi but their proof was sketchy and had unclear steps, so it gave motivation to have a better proof of this statement.
- Jérôme Durand-Lose slides
Titre: Fonctions primitives récusrsives sur les mots avec/sans concaténation
Résumé: Dans cet exposé nous revisitons les schémas de récusions primitive en ne les basant plus sur les entiers mais sur les mots (sur un alphabet fini). Dans un premier temps, nous montrons que cela permet une approche plus informaticienne de la chose et ainsi que de faire des liens avec les classes de complexité classiques. Dans un second temps, nous nous intéressons au cas où la concaténation n'est plus disponible et montrons qu'il est néanmoins possible de décider des langages non triviaux.
- Nicanor Carrasco slides
Titre: Medvedev degrees of effective subshifts on groups
Abstract: It is known that the class of effective subshifts in Z can attain al /Pi_1 Medvedev degrees. In this talk we will discuss how this result extends to the class of finitely generated groups with decidable word problem. This involves codifying translation-like actions by Z as a subshift, and takes us to the problem of the computability of translation-like actions on locally finite graphs.