Les séminaires sont communs avec l'équipe Plume (ENS Lyon) et ont lieu en salle de séminaire, premier étage du bâtiment Le Chablais, sur le site du Bourget du Lac ou à l'ENS Lyon.

Prochain séminaire :

Mercredi 28 février 2018 à 10h Eric Goles (Engineering Faculty of the Adolfo Ibanez University, Santiago, Chile),
Dynamics and Complexity of Majority Automata: application to some discrete social models

Résumé : (Masquer les résumés)
A Majority Automata consists of applying over the vertices of a undirected graph (with states 0’s and 1’s) an operator that chooses the most represented state among the neighbors of a vertex. This rule is applied in parallel over all the nodes of the graph. When the graph is a regular lattice ( in one or more dimensions) it is called the Majority Cellular Automata. In this seminar we will study the computational complexity of the following prediction problem: PRED: Given an initial configuration and a specific site initially at state a ( 0 or 1), is there a time step T≥1 such that this site changes state? The complexity of PRED is characterized by the possibility to find an algorithm that give the answer faster than the running of the automata simulation in a serial computer. More precisely, if we are able to determine an algorithm running in a parallel computer in polylog time (class NC). Otherwise, the problem may be P-Complete ( one of the most dificult in class P of Polynomial problems) or … worse. We will applied this kind of results to the discrete Schelling’s segregation model. Also we will present the Sakoda’s Social Discret model.

Le séminaire de l’équipe LIMD est sous la responsabilité de Sebastien Tavenas.
Options : Voir par date croissante . Masquer les résumés.
Autres années : 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, toutes ensemble.

Année 2018

Jeudi 17 mai 2018 à 10h, Lyon Séminaire Chocola (ENS Lyon),
TBA

Jeudi 05 avril 2018 à 10h, Lyon Séminaire Chocola (ENS Lyon),
TBA

Jeudi 29 mars 2018 à 10h Maxime Lucas (Nantes),
TBA

Jeudi 22 mars 2018 à 10h Oleg Karpenkov (Department of Mathematical Sciences, University of Liverpool),
TBA

Mercredi 21 mars 2018 à 10h Buket Eren (Galatasaray University, Istambul, Turquie.),
TBA

Jeudi 15 mars 2018 à 10h, Lyon Séminaire Chocola (ENS Lyon),
TBA

Jeudi 08 mars 2018 à 10h Étienne Miquey (Nantes),
TBA

Mercredi 28 février 2018 à 10h Eric Goles (Engineering Faculty of the Adolfo Ibanez University, Santiago, Chile),
Dynamics and Complexity of Majority Automata: application to some discrete social models

Résumé : (Masquer les résumés)
A Majority Automata consists of applying over the vertices of a undirected graph (with states 0’s and 1’s) an operator that chooses the most represented state among the neighbors of a vertex. This rule is applied in parallel over all the nodes of the graph. When the graph is a regular lattice ( in one or more dimensions) it is called the Majority Cellular Automata. In this seminar we will study the computational complexity of the following prediction problem: PRED: Given an initial configuration and a specific site initially at state a ( 0 or 1), is there a time step T≥1 such that this site changes state? The complexity of PRED is characterized by the possibility to find an algorithm that give the answer faster than the running of the automata simulation in a serial computer. More precisely, if we are able to determine an algorithm running in a parallel computer in polylog time (class NC). Otherwise, the problem may be P-Complete ( one of the most dificult in class P of Polynomial problems) or … worse. We will applied this kind of results to the discrete Schelling’s segregation model. Also we will present the Sakoda’s Social Discret model.

Jeudi 08 février 2018 à 10h, Lyon Séminaire Chocola (ENS Lyon),
TBA

Résumé : (Masquer les résumés)
TBA

Jeudi 01 février 2018 à 10h Thomas Rubiano (LIPN, Paris 13),
Implicit Computational Complexity meets Compilers

Résumé : (Masquer les résumés)
Complexity theory helps us predict and control resources, usually time and space, consumed by programs. Static analysis on specific syntactic criterion allows us to categorize some programs. A common approach is to observe the program’s data’s behavior. For instance, the detection of non-size-increasing programs is based on a simple principle : counting memory allocation and deallocation, particularly in loops. This way, we can detect programs which compute within a constant amount of space. This method can easily be expressed as property on control flow graphs. Because analyses on data's behaviour are syntactic, they can be done at compile time. Because they are only static, those analyses are not always computable or easily computable and approximations need are needed. ``Size-Change Principle'' from C. S. Lee, N. D. Jones et A. M. Ben-Amram presented a method to predict termination by observing resources evolution and a lot of research came from this theory. Until now, these implicit complexity theories were essentially applied on more or less toy languages. This thesis applies implicit computational complexity methods into ``real life'' programs by manipulating intermediate representation languages in compilers. This give an accurate idea of the actual expressivity of these analyses and show that implicit computational complexity and compilers communities can fuel each other fruitfully. As we show in this thesis, the methods developed are quite generals and open the way to several new applications.

Jeudi 25 janvier 2018 à 10h Youssef Fares (Amiens),
Autour de la conjecture de Poonen sur les polynômes quadratiques

Résumé : (Masquer les résumés)
Soit c un nombre rationnel. Considérons le polynôme φ(X) = X^2 - c. On s’intéressse aux cycles de φ dans Q. Plus précisément, on s’intéresse à l’une des conjectures de Poonen selon laquelle tout cycle de φ dans Q admet une longueur au plus égale à 3. Dans notre exposé, on discutera de cette conjecture et on rappellera les résultats connus. En suite, on utilisera des moyens arithmetiques, combinatoriaux et analytiques simples pour étudier des cas particuliers de ce problème. Les outils utilisés dans cet exposé sont accessibles aux étudiants de master 2.

Le séminaire de l’équipe LIMD est sous la responsabilité de Sebastien Tavenas.
Options : Voir par date croissante . Masquer les résumés.
Autres années : 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, toutes ensemble.