Groupe de travail

Le groupe de travail a lieu habituellement le mercredi matin à 10h30.

Groupes de travail 2011-2012 (Organisateur : Kevin Perrot)

Sébastien Tavenas (thésard dans l'équipe MC2) : Une approche de la tau-conjecture à l'aide du wronskien, mardi 15 mai 2012 à 15h00 en salle B1, ENS de Lyon site Monod.
Il était une fois, dans le Royaume de Valiant, un Roi qui voulait séparer les polynômes faciles à calculer (les gentils) de ceux difficiles à calculer (les méchants). En général, les gentils se tenaient bien sages chez eux, le mage savait qu'ils étaient gentils, mais le problème venait des méchants, un grand nombre se terraient chez les gentils et il était difficile pour le mage de les différencier. Mais un beau jour, un mage puissant lui vint en aide en lui montrant que les gentils, asservis, acceptaient de se mettre sous une forme très contraignante (somme de produits de polynômes creux de taille sous-exponentielle). Et le mage lui prédit ensuite que des très vilains (avec beaucoup de racines) n'accepteraient jamais une telle servitude. Des conseillers du Roi se demandèrent si cette prédiction (qu'ils appelèrent la tau-conjecture réelle) était vraie… Ils remarquèrent alors qu'un outil magique, le wronskien, très utilisé dans les Royaumes lointains des Equadiffs, mais déjà utilisé pas si loin par de vieux moines Polyà et Szegõ, pourrait peut-être servir.

Thierry Monteil (équipe Arith du LIRMM, Montpellier) : Mesures ergodiques en dynamique symbolique, mercredi 25 avril 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
Lorsqu’on essaye de montrer l’existence de fréquences d’apparition de motifs dans un mot infini, on est amené à étudier l’ensemble des mesures invariantes du sous-shift associé. J’essaierai d’introduire ces notions simplement, puis donnerai une majoration du nombre de mesures ergodiques invariantes d’un sous-shift en fonction de la géométrie d’objets combinatoires associés à son langage : les graphes de Rauzy et l’arbre des spéciaux à gauche. Elles s’appliquent particulièrement bien aux sous-shifts de faible complexité.

Hervé Fournier (Université Paris 7) : Monômes dans les circuits arithmétiques et hiérarchie de comptage, mercredi 18 avril 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
La représentation d'un polynôme par un circuit arithmétique le calculant est économique en terme d'espace, mais la complexité d'opérations même simples sur des polynômes ainsi représentés peut devenir importante. On s'intéresse à la complexité de deux questions à propos des polynômes représentés par des circuits arithmétiques : tester si un monôme est présent et compter les monômes. En étudiant ces questions sur diverses classes de circuits, on obtient des problèmes complets pour des sous-classes de la hiérarchie de comptage qui possédaient jusqu'à présent peu ou aucun problème complet naturel.
(Travail en commun avec Guillaume Malod et Stefan Mengel.)

Enrico Formenti (I3S, Sophia-Antipolis) : Particle dynamics in cellular automata: known results and open questions, mercredi 28 mars 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
In this talk we will review some known results about entry times for simple particle dynamical systems based on cellular automata. The second part of the talk tries to give some ideas or evidences for the proof of some open questions.

Emmanuel Jeandel (Université d'Aix-Marseille, LIRMM) : Immortalité sur les machines de Turing, mercredi 14 mars 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
Je présenterai la construction d'une fonction affine par morceaux de [0,1]^2 dans [0,1]^2 avec la particularité suivante: Partant de tout point calculable (en particulier rationnel, algébrique), l'itération de la fonction converge en temps fini vers 0. Cependant, il existe des points (non calculables) à partir desquels la fonction ne converge pas.

Luidnel MAIGNAN (LIAFA, Paris) : Points, Distances, and Cellular Automata: Geometric and Spatial Algorithmics, mercredi 7 mars 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
Many computation, complexity and algorithmic models make --for good reasons-- unrealistic spatial assumptions (e.g. constant access time to an infinite memory). Spatial computing consider physically compliant (i.e. scalable) models where computation is uniformly distributed across space and communication is local. The goal is to provide easy programming paradigms and algorithmics allowing to use the full power of such massively parallel models.
In this presentation, we study the particular case of cellular automata and consider three problems of geometrical nature: moving "computation particles" on the grid in order to uniformize their density, constructing their convex hull, and constructing a connected proximity graph between them. With a focus on the algorithmic methodology, we show how to solve these problems using the same building blocks: computation of distances fields and motions and detections based on distance patterns. The obtained solutions use constant memory and generalize over arbitrary regular grid.

Johann Makowsky (Professor at Technion, Israel Institute of Technology, Israel) : On the complexity of graph polynomials, mardi 28 février 2012 à 15h00 en salle B1, ENS de Lyon site Monod.
We discuss the complexity of various graph polynomials. In particular the Tutte polynomial and its colored variations, the interlace polynomials, and many others, satisfy a "Difficult point
property", which we shall explain in detail. Finally we discuss a general conjecture on the difficulty
of evaluating graph polynomials and propose a class of functions which may serve as an analogue to #P in the computational model BSS over the reals or complex numbers.

Yann Strozecki (ATER à Paris-Sud 11 dans l'équipe ALGO) : Énumération: méthodes logiques algébriques et géométriques, mercredi 22 février 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
Je vais présenter dans cet exposé des problèmes d'énumérations, c'est à dire qu'on veut lister toutes les solutions d'un problème. Le but est de réaliser cette tâche avec un algorithme de complexité
la plus faible possible. Dans ce cadre on s'intéresse à la fois au temps total de l'algorithme et au délai entre deux solutions.
Dans un premier temps je présenterai des algorithmes probabilistes qui permettent d'énumérer les monômes d'un polynôme. Je montrerai ensuite comment on peut utiliser ces algorithmes pour résoudre des problèmes sur des graphes, des hypergraphes, des automates probabilistes.
Dans une deuxième partie je montrerai comment représenter certains problèmes d'énumération par des formules du premier ordre contenant des variables libres du second ordre. On verra que la complexité d'énumération dépend du nombre de quantificateurs ainsi que de la structure sur lequel ces formules sont évaluées (degré bornée, largeur arborescente bornée ...).
Enfin, je vais m'intéresser a trouver des témoins qui séparent deux systèmes représentés par des automates ou des processus de décision markoviens. Comme ces témoins sont en nombre infini, on ne peut pas les énumérer, on va donc essayer de les générer uniformément. Pour cela, je vais présenter une méthode qui repose sur une marche aléatoire sur des polytopes.

Anahi Gajardo (Assistant Professor, Departamento de Ingeniería Matemática, Universidad de Concepción, Chile) : Symmetrie par rapport au temps chez les automates cellulaires, mardi 21 février 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
La reversibilite par rapport au temps est une forme forte de reversibilite, ou le systeme inverse est conjugue au systeme directe au moyen d'une function tres simple, voir une involution. Cette notion, etant important en physique, a ete neglige dans le domaine des systemes dynamiques discretes, notament chez les automates cellulaires.
Dans cette exposé on definit formellement cette propriete et on etudie ses implications ; pour finir avec son indecidibilite en dimension 2.

Pascal Koiran (Professeur à l'ENS de Lyon, LIP équpe MC2) : Random graphs without large dense subgraphs: are they hard to certify?, mercredi 15 février 2012 à 11h15 en salle B1, ENS de Lyon site Monod.
Given a graph on n vertices, is there a subgraph induced by k vertices with edge density at least 0.5+epsilon ? For suitable values of the parameters k and epsilon, the answer is NO for most graphs.
It then makes sense to ask for an algorithm certifying that most graphs do not contain any dense k-subgraph. We propose efficient algorithms for certain values of the parameters, and identify other values for which this problem seems hard.
This work is motivated by applications to compressed sensing, and more precisely to the computational complexity of the restricted isometry
property (no background in this area will be assumed).

Olivier Bournez (Professeur et Directeur du laboratoire d'Informatique de l'Ecole Polytechnique, Paris) : Sur la complexité algorithmique de résoudre et de calculer avec des équations différentielles, mercredi 8 février 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
On s'intéressera à différents problèmes reliés aux équations différentielles motivés par des modèles de calculs analogiques à temps continu.
Plus précisément, on verra
1- comment la calculabilité dans certains modèles de calculs analogiques se ramène à des problèmes simples sur des classes simples d'équations différentielles.
2- que comparer les modèles classiques de la complexité et de la calculabilité aux modèles analogiques revient à se poser des questions sur la complexité algorithmique de résoudre de telles équations.
3- que les méthodes efficaces de l'analyse numérique pour cela ne sont pas efficaces/polynomiales dans ce contexte.
4- que l'on peut bien résoudre les équations différentielles en temps polynomial, avec un peu d'ingéniosité et d'originalité.

Pablo Arrighi (Université de Grenoble I - ENS de Lyon) : Causal graph dynamics, mercredi 18 janvier 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
We capture, at the formal level, the idea of a labelled graph which evolves in time, but under the natural constraint that information can only ever be transmitted at a bounded speed, where the notion of distance is given by the graph itself. Another way to say this is that we generalize the Cellular Automata model of computation, to a model of causal dynamics over arbitrary labelled graphs. Again, the graph is allowed to change under the dynamics, but at the same time it is a constraint over the dynamics. The provided definition of causal graph dynamics is simple and robust. For instance, we show that causal graph dynamics are stable under composition and restriction to radius one. In the finite case some fundamental facts of Cellular Automata theory carry through: causal graph dynamics admit a characterization as continuous functions, and they are stable under inversion. We provide some examples suggesting a wide range of applications, from complex systems science to theoretical physics.
Keywords: Boolean networks, Dynamical networks, Generalized Cayley Cellular Automata, Regge calculus.
Joint work with Gilles Dowek.

Nathalie Aubrun (University of Turku, Finlande) : Problèmes de pavages sur les groupes de Baumslag-Solitar, mercredi 11 janvier 2012 à 10h30 en salle B1, ENS de Lyon site Monod.
En 1966, Berger montre que le problème de la pavabilité du plan par un jeu de tuiles fini (problème du domino) est indécidable. Lorsque les pavages sont définis non plus dans le plan discret Z^2 mais sur un groupe finiment présenté, et si ce groupe est virtuellement libre (c'est-à-dire qu'il possède un sous-groupe libre d'indice fini), alors le même problème est décidable. L'implication réciproque est toujours un problème ouvert.
Dans cet exposé on présentera les groupes de Baumslag-Solitar, qui sont les groupes à deux générateurs définis par la relation a.b^m=b^n.a. Sur ces groupes, on montrera d'une part l'existence de jeu de tuiles fortement apériodique, et d'autre part l'indécidabilité du problème du domino.

Jean Mairesse (LIAFA, Université Paris 7) : Automates cellulaires et probleme de classification de la densite, mercredi 30 novembre 2011 à 10h30 en salle de conseil du LIP.
Soit un graphe infini dont les noeuds sont initialement etiquetes par des variables aleatoires de Bernoulli de parametre p independantes. On souhaite construire un automate cellulaire (deterministe ou
probabiliste) ou un systeme de particules en interaction de portee finie, evoluant sur l'espace des configurations du graphe, et permettant de decider si p est plus petit ou plus grand que 1/2. Precisement, les trajectoires doivent converger vers la configuration "tout 0" si p<1/2 et vers la configuration "tout 1" si p>1/2. On propose des solutions au probleme pour: (i) la grille de dimension au moins 2; (ii) les arbres infinis reguliers de degre au moins 3. Pour la ligne, le probleme est ouvert et il est sans doute relie a la "conjecture des taux positifs". On propose des solutions conjecturales qui ont ete testees numeriquement. Travail commun avec Ana Busic, Nazim Fates et Irene Marcovici.

Stéphane Attal (Institut Camille Jordan, Lyon) : Marches aléatoires quantiques ouvertes, mercredi 9 novembre 2011 à 10h30 en salle de conseil du LIP.
Je vous présenterai des résultats concernant un nouveau modèle de marches aléatoires quantiques, développé par Christophe Sabot et moi. Ce modèle se distingue des modèles usuels de marches quantiques par son caractère dissipatif. On observe en particulier un comportement typique de ces marches qui est quantique, pas à pas, mais qui pourtant est gaussien asymptotiquement. L'exposé sera introductif et ne nécessite aucune connaissance préalable sur les marches aléatoires.

Guillaume Theyssier (LAMA, Chambéry) : Panorama informel de la théorie des simulations intrinsèques pour les automates cellulaires classiques, mardi 25 octobre 2011 à 15h en salle B1.
La théorie des pré-ordres de simulation entre automates cellulaires est développée depuis plus de 15 ans par "l'école lyonnaise" (autour de J. Mazoyer). Il s'agit littéralement de "mettre en ordre" le problème de classification des comportements très divers observés. À l'image du modèle des automates cellulaires, ces ordres s'appuient sur des ingrédients très simples et fournissent néanmoins des structures riches à travers lesquelles étudier les problématiques classiques du domaine, à commencer par celle de l'universalité. Le but de cet exposé est de fournir un panorama de cette théorie. Le mode de présentation se veut plutôt informel et permettra les développements à la demande sur des aspects particuliers.

Archives du groupe de travail

http://www.ens-lyon.fr/LIP/MC2/groupe-de-travail/ | Saved Thursday, May 10th, 2012 - 2:34 PM