Cette page rassemble les informations et ressources relatives
au séminaire tutoré du
M2 IMD,
organisé par
Shantanu Das (LIS)
et
Lionel Vaux Auclair (I2M).
Le programme du séminaire est organisé en deux temps:
-
les premières séances sont assurées par des chercheurs et chercheuses des équipes impliquées dans le master;
-
les séances suivantes sont consacrées à des présentations d’articles travaillés par les étudiantes et étudiants.
Tous les exposés sont donnés en anglais. Ils ont généralement lieu le jeudi après-midi.
Pour les présentations d’articles :
-
Chaque étudiante ou étudiant choisit un article de recherche, en anglais, parmi les
propositions ci-dessous.
-
Ce choix est arrêté au plus tard le 16 décembre.
-
L’exposé donné au séminaire consiste en la présentation de l’article choisi.
Cette présentation doit être focalisée sur les aspects classiques (contexte, objectif, résultats obtenus, perspectives) et détailler un peu la partie technique de l'article.
Séances
- 9 décembre, 14h: Étienne Miquey (I2M)
- The benefits of sequent calculus
- support de l’exposé
- 16 décembre, 14h: Yves Lafont (I2M)
- Towards an algebraic theory of classical and quantum boolean circuits
- 6 janvier, 14h: Karoliina Lehtinen (LIS)
- A bit of nondeterminism makes pushdown automata expressive and succinct
- slides
- 13 janvier, 14h:
-
Reda El Masdouri:
Finding the longest isometric cycle in a graph
- slides
- 20 janvier, 14h:
-
Alexandre Coppé:
Tiling simply connected regions with rectangles
-
Raffaele Di Donna:
An Anti-Locally-Nameless Approach to Formalizing Quantifiers
- slides
-
Alonso Herrera:
On topological dynamics of Turing machines
- 3 février, 14h:
-
Élisabeth Novikoff:
On Non-Computable Functions
- slides
-
Léah Tapin:
Generators and relations for n-qubit Clifford operators
- slides
-
Jean-Baptiste Vienney:
A Categorical Quantum Logic
- (black board talk)
- 10 février, 14h:
-
Yahia Idriss Benalioua:
Cellular Automata and Powers of p/q
- slides
-
Thomas Usimaki:
Parallel recognition of series-parallel graphs
Articles proposés
Pour chaque article, on indique la personne qui l’a proposé :
cette personne acceptera probablement (mais pas nécessairement)
de correspondre et discuter avec vous pour éclairer votre lecture si nécessaire.
-
On Non-Computable Functions
de T. Rado.
-
Proposé par Kevin Perrot (LIS), qui écrit:
Pour ouvrir la discussion/présentation je conseille la lecture de ce billet de blog par Scott Aaronson.
-
-
Tiling simply connected regions with rectangles
de I. Pak et J. Yang.
-
Proposé par Kevin Perrot (LIS).
-
Towards an Algebraic Theory of Boolean Circuits
d’Yves Lafont.
-
Proposé par Yves Lafont (I2M).
-
Generators and relations for n-qubit Clifford operators
de P. Selinger.
-
Proposé par Yves Lafont (I2M).
-
Cellular Automata and Powers of p/q
de J. Kari et J. Kopra.
-
Proposé par Pierre Guillon (I2M), qui écrit:
- AC et théorie des nombres,
- un AC qui fait des multiplications et du coup des orbites parcourent tous les mots finis.
-
Groups defined by Automata
de L. Bartholdi, et P. V. Silva.
-
Proposé par Pierre Guillon (I2M), qui écrit:
survol sur les groupes automatiques, puis sur les groupes d'automates.
-
Decidability of the HD0L ultimate periodicity problem
de F. Durand.
-
Proposé par Pierre Guillon (I2M).
-
Episturmian words: a survey
de A. Glen et J. Justin.
-
Proposé par Pierre Guillon (I2M), qui écrit:
survol sur une généralisation des mots sturmiens à un alphabet infini.
-
On time-symmetry in cellular automata
de A. Gajardo, J. Kari, A. Moreira.
-
Proposé par Guillaume Theyssier et Pierre Guillon (I2M), qui écrivent:
- quand la dynamique est proche de la dynamique inverse…;
- facile sauf la fin, nouveau par rapport au cours mais connecté à des notions vues, permet de faire une belle présentation.
-
Periodicity and Immortality in Reversible Computing
de J. Kari et N. Ollinger:
-
Proposé par Guillaume Theyssier et Pierre Guillon (I2M), qui écrivent:
- indécidabilité de la périodicité des machines de Turing, puis des AC;
- gros résultat, beau mélange de modèles de calcul et systèmes dynamiques.
-
On the Undecidability of the Tiling Problem
de J. Kari:
-
Proposé par Guillaume Theyssier et Pierre Guillon (I2M), qui écrivent:
une preuve de l'indécidabilité du problème du pavage (y compris
dans le plan hyperbolique) en passant par l'indécidabilité de
la mortalité des fonctions affines par morceaux.
-
A categorical theory of patches
de S. Mimram et C. Di Giusto.
-
Proposé par Lionel Vaux Auclair (I2M), qui écrit:
Une approche catégorique de la conception d’un
logiciel de gestion de versions,
qui a inspiré une implémentation
prometteuse à la fois en termes de fonctionnalités et de performances.
-
An Anti-Locally-Nameless Approach to Formalizing Quantifiers
d’O. Laurent.
-
Proposé par Lionel Vaux Auclair (I2M), qui écrit:
Une proposition originale pour formaliser la liaison de
variables par les quantificateurs, en évitant les problèmes de
captures dans la substitution.
-
Linear lambda terms as invariants of rooted trivalent maps
de N. Zeilberger.
-
Proposé par Lionel Vaux Auclair (I2M), qui écrit:
Ce papier revisite une correspondance précédemment établie
entre une certaine classe de λ-termes
et une certaine classe de cartes combinatoires
(qui sont une représentation combinatoire de graphes plongés
sur des surfaces et considérés à déformation près).
C’est un peu technique mais au bout du chemin on trouve
une reformulation du théorème des 4 couleurs
comme une propriété de typage.
-
Graph theory and probability
de P. Erdös.
-
Proposé par Lionel Nguyen Van Thé (I2M), qui écrit :
Il s'agit de l'article d'Erdös qui a lancé la méthode probabiliste en théorie
des graphes (et plus généralement, en combinatoire), donc d'intérêt historique
certain.
-
Finding the longest isometric cycle in a graph
de Daniel Lokshtanov.
Discrete Applied Mathematics 157(12): 2670-2674 (2009)
-
Proposé par Jérémie Chalopin (LIS), qui écrit :
Un algorithme polynomial pour trouver un plus long cycle
isométrique (c'est à dire que les distances entre les sommets du cycle sont
les mêmes dans le cycle et dans le graphe). Un résultat un peu surprenant
parce que de nombreuses variantes de recherches de plus longs cycles dans un
graphe sont NP-difficiles.
-
Views in a Graph: To Which Depth Must Equality Be Checked?
de Julien M. Hendrickx.
IEEE Trans. Parallel Distrib. Syst. 25(7): 1907-1912 (2014)
-
Proposé par Jérémie Chalopin (LIS), qui écrit :
La vue d'un sommet v dans un graphe G est un arbre (infini) dont
les sommets correspondent aux chemins issus de v dans G. Si deux sommets ont
la même vue, ils ont la même vue de hauteur k (on ne considère que les chemins
de longueur au plus k). Dans cet article, l'auteur cherche pour quelles
valeurs de k, la réciproque est vraie.
-
Infinite λ-calculus and non-sensible models
d’Alessandro Berarducci.
-
Proposé par Rémy Cerda (I2M), qui écrit:
Il s'agit de l'une des premières présentations d'un λ-calcul
infinitaire (les termes et les séquences de réduction peuvent
être infinis), contemporaine de celle de Kennaway et al.
Ici, il s'agit de la version la plus « sauvage » du calcul
infinitaire mais elle est présentée de manière très lisible,
sans bureaucratie sur l'infini (ordinaux, coinduction, …).
L'auteur reprend plein de notions classiquement définies en
λ-calcul (résidus, réduction de tête, standardisation, …), et
aboutit à un modèle du λ-calcul qui raffine celui des arbres
de Böhm.
-
A semantics of evidence for classical arithmetic
de Thierry Coquand.
-
Proposé par Étienne Miquey (I2M), qui écrit:
Une interprétation des formules de l'arithmétiques classiques via une
sémantique définissant une notion de jeu.
-
On the Computational Content of the Axiom of Choice
de Stefano Berardi, Marc Bezem et Thierry Coquand.
-
Proposé par Étienne Miquey (I2M), qui écrit:
Une interprétation calculatoire de l'axiome du choix à travers une traduction
négative (celui là est un peu plus costaud que le précédent).
-
Parallel recognition of series-parallel graphs
de David Eppstein.
-
Proposé par Arnaud Labourel (LIS).
-
Optimal constrained graph exploration
de C. Duncan, S. Kobourov, et A. Kumar.
-
Proposé par Arnaud Labourel (LIS).
-
Towards a Complexity Theory for Local Distributed Computing
de P. Fraigniaud, A. Korman, and D. Peleg.
-
Proposé par Shantanu Das (LIS).
-
Many Random Walks Are Faster Than One
de N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker et M. Tuttle.
-
Proposé par Shantanu Das (LIS).
-
Knowledge and common knowledge in a distributed environment
de Joseph Y. Halpern et Yoram Moses.
-
Proposé par Nicola Olivetti (LIS), qui écrit:
Un article classique et de valeur historique pour l'application des
logiques épistémiques à l'analyse des systèmes distribués.
-
The Secret of My Success
de Hans P. van Ditmarsch et Barteld P. Kooi.
-
Proposé par Nicola Olivetti (LIS), qui écrit:
Article technique mais aussi ludique: on utilise la Dynamic Epistemic
Logic pour analyser des jeux et des puzzles classiques ("Muddy Children")
et en particulier le rôle de "success formulas"
-
A Categorical Quantum Logic
de S. Abramsky et R. Duncan
-
Proposé par Lionel Vaux Auclair (I2M) sur une suggestion de J.-B. Vienney.
-
On topological dynamics of Turing machines
de Petr Kurka.
-
Proposé par Cristóbal Rojas (Chile).