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 sur le campus de Luminy.
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 10 novembre.
-
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
- 22 novembre, 14h30, E.01.12:
- Pierre Arnoux (I2M):
Sequences of minimal complexity and the two lengths theorem.
- Mathematicians as well as computer scientists like to measure the complexity of
sets, languages, words, programs… They define hierarchies of complexity, with
measures of entropy, or recursive sets, and various machines (Turing,
automata…). Usually, they are concerned with high complexity, and the top of
hierarchy (computable sets…). In this lecture, we will study the opposite:
what is the bottom of the classification? What are the least complex sequences,
languages or tilings? We will show that this question gives rise to simple and
beautiful theorems, and a number of surprising results and questions, linking
theoretical computer science, algebra, geometry and number theory.
- 1er décembre, 14h, F.04.14:
- Oscar Defrain (LIS):
A linear-delay algorithm for minimal dominating sets enumeration in split graphs.
-
A dominating set in a graph G is a subset D of vertices such that
every vertex of G is either in D or adjacent to a vertex in D. It is called
minimal if no proper subset is a dominating set. In this talk, we present an
easy algorithm from [Kanté et al., SIDMA 2014] to list minimal dominating sets
in split graphs, i.e., graphs whose vertices may be partitioned into a clique
and an independent set.
- 15 décembre, 14h, E.01.12:
- Marc Chouraqui:
The Busy Beaver Competition: a historical survey
- Guillaume Vidal:
Regular Languages of Words over Countable Linear Orderings
- 12 janvier, 13h30, E.02.08:
- Jade Audouard:
On generating all maximal independent sets
- Kossi Etse:
Graph theory and probability
- Vincent Sommella:
Linear lambda terms as invariants of rooted trivalent maps
19 janvier 26 janvier, 13h30, E.02.05:- Seny Fadera:
Algorand: Scaling Byzantine Agreements for Cryptocurrencies
- Jacopo Furlan:
On the Computational Content of the Axiom of Choice
- Raphaël Henry:
On the translation of languages from left to right
26 janvier 2 février, 13h30, E.02.13- Stefano Catozi:
(Leftmost-Outermost) Beta Reduction is Invariant, Indeed
- Yannis Coutouly:
Chromatic subdivision of a simplicial complex
- Marius Rolland:
Min-Max Tree Covers of 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 the translation of languages from left to right
de D. Knuth.
Information and Control
Volume 8, Issue 6, December 1965.
-
Proposé par Alexey Muranov (I2M).
-
Assigning meaning to programs
de Robert Floyd.
In Schwartz, J.T. (ed.). Mathematical Aspects of Computer Science. Proceedings of Symposium on Applied Mathematics. Vol. 19. American Mathematical Society,
1967.
-
Proposé par Alexey Muranov (I2M).
-
Linear lambda terms as invariants of rooted trivalent maps
de N. Zeilberger.
Journal of Functional Programming, Volume 26, 2016.
-
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.
-
(Leftmost-Outermost) Beta Reduction is Invariant, Indeed
de Beniamino Accattoli & Ugo Dal Lago.
Logical Methods in Computer Science, March 9, 2016, Volume 12, Issue 1.
-
Proposé par Lionel Vaux Auclair (I2M), qui écrit:
Ce papier démontre que le nombre d’étapes de β-réduction
gauche menant à une forme normale est
une notion raisonnable de temps de calcul.
L’article est long et technique mais bien organisé : on peut
naviguer dedans pour en tirer l’essentiel sans nécessairement
détailler toutes les étapes.
-
Graph theory and probability
de P. Erdös.
Canadian Journal of Mathematics, Volume 11, 1959.
-
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.
-
Infinite λ-calculus and non-sensible models
d’Alessandro Berarducci.
Theoretical Computer Science
Volume 212, Issues 1–2, 6 February 1999.
-
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.
-
Min-Max Tree Covers of Graphs
de G. Even, N. Garg, J. Konemann, R. Ravi & A. Sinha.
Operations Research Letters, vol. 32, pp. 309-315, 2004.
-
Proposé par Shantanu Das (LIS), qui écrit:
Comment couvrir un arbre avec k sous-arbres de taille la plus petite possible?
Un problème classique avec beaucoup d'applications.
-
Balanced Allocations
de Y. Azar, A. Z. Broder, A. R. Karlin, E. Upfal.
In
Proceedings of the 26th ACM Symposium on Theory of Computing (STOC),
1994.
-
Proposé par Shantanu Das (LIS).
-
Cooperative mobile guards in grids
d’Adrian Kosowski, Michał Małafiejski, and Paweł Żyliński.
Computational Geometry 37.2, 2007.
-
Proposé par Shantanu Das (LIS).
-
Regular Languages of Words over Countable Linear Orderings
de Gabriele Puppis, Thomas Colcombet, Olivier Carton.
Proceedings of ICALP 2011.
-
Proposé par Nathan Lhote (LIS).
-
Towards an Algebraic Theory of Boolean Circuits
d’Yves Lafont.
Journal of Pure and Applied Algebra 184 (2-3), p. 257–310, Elsevier (2003).
-
Proposé par Yves Lafont (I2M).
-
Generators and relations for n-qubit Clifford operators
de Peter Selinger.
Logical Methods in Computer Science 11(2:10), p. 1–17 (2015).
-
Proposé par Yves Lafont (I2M).
-
On generating all maximal independent sets
de D. S. Johnson, M. Yannakakis & C. H. Papadimitriou.
Information Processing Letters, 27(3), 1988.
-
Proposé par Oscar Defrain (LIS).
-
A semantics of evidence for classical arithmetic
de Thierry Coquand.
The Journal of Symbolic Logic, Volume 60, Issue 1, 1995.
-
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 & Thierry Coquand.
The Journal of Symbolic Logic, Volume 63 , Issue 2 , 1998.
-
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).
-
A six-state minimal time solution to the firing squad synchronization problem
de Jacques Mazoyer.
Theoretical Computer Science
Volume 50, Issue 2, 1987.
-
Proposé par Kévin Perrot (LIS), qui écrit:
Le mythique automate cellulaire à 6 états du français Jacques Mazoyer.
L'existence d'une solution à 5 états au problème de synchronisation du
peloton est toujours ouvert !
-
The Busy Beaver Competition: a historical survey
de Pascal Michel.
2019.
-
Proposé par Kévin Perrot (LIS), qui écrit:
La compétition du castor affairé bat son plein depuis 1962. Mais à
quoi ressemblent les gagnants actuels d'un jeu qui *nécessite* notre
intelligence ?
-
The theory of timed automata
de R. Alur & D. Dill.
In: de Bakker, J.W., Huizing, C., de Roever, W.P., Rozenberg, G.
(eds) Real-Time: Theory in Practice. REX 1991. Lecture Notes in
Computer Science, vol 600, 1992.
-
Proposé par Karoliina Lehtinen (LIS).
-
Alternating tree automata, parity games, and modal mu-calculus
de Thomas Wilke.
Bulletin of the Belgian Mathematical Society--Simon Stevin 8.2 (2001): 359-391.
-
Proposé par Karoliina Lehtinen (LIS).
-
Algorand: Scaling Byzantine Agreements for Cryptocurrencies
de Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos & Nickolai Zeldovich.
In Proceedings of the 26th Symposium on Operating Systems Principles (SOPS'17), 2017.
-
Proposé par Corentin Travers (LIS).
-
On the Space Complexity of Randomized Synchronization
de Faith E. Fich, Maurice Herlihy & Nir Shavit.
Journal of ACM 45(5): 843-862 (1998).
-
Proposé par Corentin Travers (LIS), qui écrit:
Sur la complexité en mémoire de quelques algorithmes en mémoire partagée.
-
Optimal constrained graph exploration
de Christian A. Duncan, Stephen G. Kobourov & V. S. Anil Kumar.
ACM Trans. Algorithms 2, 3 (July 2006).
-
Proposé par Arnaud Labourel (LIS).
-
Exploring Unknown Undirected Graphs
de Petrişor Panaite & Andrzej Pelc.
Journal of Algorithms, Volume 33, Issue 2, 1999, pages 281-295.
-
Proposé par Arnaud Labourel (LIS).
-
Chromatic subdivision of a simplicial complex
de Dmitry N. Kozlov
Homology, Homotopy and Applications Volume 14 (2012) Number 2, Pages: 197 – 209.
-
Proposé par Emmanuel Godard (LIS).
-
Non-idempotent intersection types for the Lambda-Calculus
de A. Bucciarelli, D. Kesner & D. Ventura.
Logic Journal of the IGPL, 25(4):431--464, 2017.
-
Proposé par Lionel Vaux Auclair (I2M), qui écrit:
Ce papier revisite des caractérisations de la normalisation
(de tête, faible, forte, etc. ) au moyen
de systèmes de types avec intersection non idempotente.
C’est un outil récent qui provient de travaux en logique linéaire
et qui a trouvé sa place dans la boîte à outils du
logicien/sémanticien dans la dernière décennie.