Le séminaire de l’équipe LIMD est sous la responsabilité de Xavier Provençal.
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, toutes ensemble.

Année 2017

Lundi 27 mars 2017 à 10h Manfred Madritsch (Nancy),
Systèmes dynamiques et l'équirépartition des suites

Résumé : (Masquer les résumés)
Cet exposé considère l'amélioration de Furstenberg du théorème de récurrence de Poincare. Nous commençons avec ce théorème et faisons une connexion avec la théorie d'équirépartition des suites. Les rotations du cercle donnent des exemples élémentaires des suites équiréparties et des systèmes dynamique. En considèrent leur généralisations le théorème de van der Corput joue un rôle central et nous analysons ce théorème et ses conséquences. Le concept d'un ensemble de van der Corput boucle la boucle avec le théorème de Furstenberg-Sárközy.

C'est de travail conjoint avec Robert Tichy de l'Université Technique de Graz.

Jeudi 16 mars 2017 à 10h Lionel Nguyen Van Thé (Aix-Marseille Université),
Théorie de Ramsey structurale et dynamique topologique

Résumé : (Masquer les résumés)
L'objet de la théorie de Ramsey est l'étude de l'apparition nécessaire de la régularité au sein des structures de grande taille, même lorsque ces dernières sont soumises à des partitions. Par exemple, le théorème de Ramsey affirme que tout graphe infini admet un sous-graphe induit complet (où tous les sommets sont reliés à tous les autres) ou indépendant (où aucun sommet n'est relié à aucun autre). De manière équivalente, pour toute partition finie de l'ensemble des paires de nombres naturels, il existe un ensemble infini de naturels dont les paires sont toutes dans la même partie. Un autre exemple est donné par le théorème de van der Waerden, qui affirme que pour toute partition des entiers naturels en un nombre fini de parties, l'une des parties contient nécessairement des progressions arithmétiques de longueur finie arbitrairement grande (il se peut en revanche qu'aucune des parties ne contienne de progression arithmétique infinie).

Le but de cet exposé sera de présenter dans quelle mesure des résultats de ce type peuvent être obtenus dans des contextes où plus de structure apparaît (espaces vectoriels, espaces métriques, graphes, graphes dirigés, etc), et de montrer comment, à partir des travaux de Kechris, Pestov et Todorcevic de 2005, ces résultats peuvent être utilisés pour démontrer des résultats de dynamique topologique, tels que le théorème suivant, dû à Pestov : Soit G le groupe d'automorphismes des rationnels (vus comme l'unique ordre total dense sans point d'extrémité). Alors, lorsqu'il est équipé de la topologie adéquate, G est extrêmement moyennable, c'est-à-dire que toute action continue de G par homéomorphismes sur un espace compact admet un point fixe.

Jeudi 16 février 2017 à 10h Jean-Bernard Stefani (INRIA),
TBA

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

Jeudi 02 février 2017 à 14h, Tarentaise 108 Anupam Das (ENS Lyon),
Monotonicity in Logic and Complexity

Résumé : (Masquer les résumés)
Monotonicity is a fundamental notion in mathematics and computation. For usual real-valued functions R → R this simply corresponds to the notion that a function is increasing (or decreasing) in its argument, however this can be parametrised by any partially ordered domain and codomain we wish. In computation we deal with programs that compute Boolean functions, {0,1}* → {0,1}*. Restricting to increasing functions over this structure can be seen as prohibiting the use of negation in a program; for instance monotone Boolean functions are computed by Boolean circuits without NOT gates. The idea of restricting negation scales to other models of computation, and for some important classes of functions the formulation is naturally robust, not depending on the particular model at hand, e.g. for the polynomial-time functions. Monotone computational problems abound in practice, e.g. sorting a string and detecting cliques in graphs, and 'nonuniform' monotone models of computation, such as monotone circuits, have been fundamental objects of study in computational complexity for decades.

In this talk I will propose a project that develops *logical* characterisations of monotone complexity classes, via a proof theoretic approach. Namely, the project will identify theories of arithmetic whose formally representable functions coincide with certain monotone classes, and also develop fundamental recursion-theoretic programming languages in which to extract the monotone functions themselves. In particular the project focusses on the role of structural proof theory, i.e. the duplication and erasure of formulae, in controlling monotonicity.

Jeudi 02 février 2017 à 10h Andrea Frosini (Florence),
Reconstruction of 2-convex polyominoes

Résumé : (Masquer les résumés)
A polyomino P is called 2-convex if for every two cells belonging to P, there exists a monotone path included in P with at most two changes of direction. We present some tomographical properties of 2-convex polyominoes from their horizontal and vertical projections and gives an algorithm that reconstructs them from a given couple of projections. We discuss its complexity.

Jeudi 26 janvier 2017 à 10h Lama Tarsissi (LAMA),
Second order balance property on Christoffel words

Résumé : (Masquer les résumés)
Balanced words have been studied a lot in the last decades. In particular, Christoffel words that are a special case of finite balanced words. In this talk, I introduce the Balance matrix that studies the balancedness of these words and I define some tools to extend this property by defining a second order of balancedness. I recall some properties about the continued fraction development and the Stern-Brocot tree to prove a recursive formula based on the shape of the path from the root of the Stern-Brocot. Finally, I show that among all infinite paths in the Stern-Brocot tree, the one that converges to φ, the golden ratio, minimizes the growth of the second order balance.

Jeudi 19 janvier 2017 à 10h Pawel Sobocinski (Southampton),
Programming recurrence relations

Résumé : (Masquer les résumés)
Recurrence relations have been of interest since ancient times. Perhaps the most famous is the Fibonacci numbers, where each additional term in the sequence is obtained as the sum of the previous two. I will show how we can use a graphical language of string diagrams–a “graphical linear algebra”–to reason about recurrence relations, and as a bonus, obtain efficient implementations. This application comes from a general string diagrammatic theory of signal flow graphs–a model of computation originally studied by Claude Shannon in the 1940s–developed in collaboration with Filippo Bonchi and Fabio Zanasi, and published at CONCUR 2014 and PoPL 2015.

Le séminaire de l’équipe LIMD est sous la responsabilité de Xavier Provençal.
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, toutes ensemble.