Pour faire plaisir à Antoine, on découvrira de quoi il en retourne en regardant ici :
https://christophebertault.fr/documents/articles/Article%20-%20La%20theorie%20de%20Galois%20en%20MPSI.pdf

En dimension 1, sur Z, les sous-shifts de type fini (et sofiques) peuvent être vus comme l'ensemble des chemins bi-infinis sur un graphe (automate) donné : les suites bi-infinies des arêtes (labels des arêtes) traversées. Deux sous-shifts sont isomorphes (on dit aussi conjugués) s'il existe une fonction continue, bijective et commutant avec la translation qui permet de transformer l'un en l'autre. Il est connu depuis les années 70 que l'on peut décider l'isomorphisme dans le cas des sous-shifts sur N. Le problème est encore ouvert pour Z. Je propose dans ce GLT de parler de la preuve pour N et de pourquoi elle ne fonctionne pas sur Z.

Le classement Elo est utilisé pour donner des scores aux joueurs d'échecs. Pour faire quelque chose qui tient la route, il n'est pas si simple... Je trouverai intéressant de s'intéresser et d'essayer de comprendre.

A ALEA, il y a deux ans, on avait eu un exposé long sur la (Strong) Exponential Time Hypothesis, qui dit en gros que SAT peut pas être résolu en O(c^n) avec c < 2.

De ce postulat-là, on pouvait faire des réductions et prouver des bornes inférieures polynomiales sur certains problèmes algorithmiques. Par exemple, le problème d'alignement de séquences, assez classique car c'est un problème de prog dynamique qui se résout en O(n^2), ne peut pas être résolu en O(n^(2-epsilon)) si SETH est vrai.

Un GLT sur la SETH pourrait être bénéfique à Julien D. pour le problème d'approximation dans les arbres cartésiens, et à Paul et moi pour une collab avec Laurent Bulteau.

On pourrait se baser sur les slides d'ALEA de Bruno Escoffier : https://www.cirm-math.fr/RepOrga/2887/Slides/EscoffierAlea.pdf