Séminaire tutoré

M2 IMD, 2021—2022

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:

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 :

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).

Dernière mise à jour
le 11 février 2022.

XHTML et CSS valides?