January 2018 - Seminaire.calin

Seminaire CALIN demain : deux exposes
by Thierry Monteil 29 Jan '18

29 Jan '18

Bonjour, demain mardi 30 janvier 2018 à 14h00 en B107, Mohab Safey El Din nous parlera de : The quest of asymptotically fast algorithms for polynomial system solving over the reals Résumé : Polynomial systems arise in many areas of engineering sciences and computer science. Most of the time, the end-user expects some information about the real solution set of the system under study. Algorithmic problems encompass which appear frequently is to decide the existence of real solutions, compute sample points in each connected component of the set under study, compute a description of this set on some affine space or answer connectivity queries. All these problems are NP-hard and, actually the best known complexities to solve them are exponential in the number of variables. Moreover, because of the non-linearity of the considered systems, reliable issues are important. In this talk, I will give an overview of computer algebra algorithms for solving these problems with a focus on those which conciliate practical efficiency with asymptotically optimal complexity. Puis, à 15h00 en B107, Wenjie Fang nous parlera de : Aspects énumératifs et bijectifs des cartes combinatoires Résumé : Les cartes combinatoires, étant un modèle riche, portent plusieurs aspects : algébrique, géométrique, bijective, ... Dans cet exposé, je présente un ensemble de résultats et de connexions dans le domaine de l'énumération des cartes, obtenus à travers des aspects différents. Nous verrons comment utiliser les outils algébrique, comme caractères du groupe symétrique et équations fonctionnelles, à énumérer les cartes. Nous verrons aussi comment étudier les autres objets dans la combinatoire, ici les intervalles du treillis de Tamari, à travers de l'aspect bijectif des cartes. À demain, Thierry

1 0

Seminaire CALIN a 14h demain
by Thierry Monteil 22 Jan '18

22 Jan '18

Bonjour, demain mardi 23 janvier 2018 à 14h00 en B107 (après l'AG qui aura lieu à midi dans l'amphi gauche de l'IUT de Villetaneuse), Vincent Jugé nous parlera de : Uniform generation of infinite concurrent runs: the case of trace monoids. Résumé : We introduce an algorithm for the uniform generation of infinite runs in concurrent systems under a partial order probabilistic semantics. Using trace monoids as concurrency models, we will first focus on the notion of a uniform distribution on infinite traces in general and on the simulation of such a distribution. Then, we will introduce our algorithm, which aims at simulating a uniform distribution in a distributed context. This algorithm outputs on-the-fly approximations of a theoretical infinite run, the latter being distributed according to the exact uniform probability measure. The average size of the approximation grows linearly with the time of execution of the algorithm, and the execution of the algorithm only involves distributed computations, provided that some - costly - precomputations have been done. This presentation is based on a joint work with Samy Abbes. À demain, Thierry

1 0

Seminaire CALIN a 14h aujourd'hui
by Thierry Monteil 16 Jan '18

16 Jan '18

Bonjour, Aujourd'hui mardi 16 janvier 2018 à 14h00 en B107, Pierre Rousselin nous parlera de : Chute de dimension pour les marches aléatoires sur les arbres aléatoires Résumé : Nous nous intéressons à différents modèles d'arbres aléatoires et aux marches aléatoires sur les sommets de tels arbres. Dans le cas où la marche aléatoire est transiente, la marche part presque sûrement vers l'infini en empruntant un rayon aléatoire. La loi de ce rayon est appelée la mesure harmonique sur le bord de l'arbre. Un phénomène de chute de dimension se produit : cette mesure harmonique est presque sûrement concentrée sur une partie petite (au sens de la dimension de Hausdorff) du bord de l'arbre. Autrement dit, les trajectoires de la marche aléatoires sont presque sûrement comprises dans un sous-arbre beaucoup plus fin que l'arbre original. Cette théorie a été initiée par Russel Lyons, Robin Pemantle et Yuval Peres dans les années 1990. Plus récemment, Nicolas Curien, Jean-François Le Gall, puis Shen Lin ont étudié ce phénomène sur un autre modèle d'arbres aléatoires. Nous rappellerons leurs résultats et discuterons des généralisations (https://arxiv.org/abs/1708.06965 et https://arxiv.org/abs/1711.07920) sur lesquelles nous avons travaillé. Desole pour le retard de l'annonce, Thierry

1 0

Seminaire Calin demain mardi 9 janvier
by Thierry Monteil 08 Jan '18

08 Jan '18

Bonjour et bonne année, demain mardi 9 janvier 2018 à 14h00 en B107, Jordan Emme nous parlera de : Produits de matrices aléatoires et application arithmétique Résumé : Dans un travail en commun avec Pascal Hubert, nous étudions les lois limites de certains produits de matrices et en donnons une application arithmétique: On note s_2 la fonction somme des chiffres en base 2 et on considère, pour tous paramètres entiers a et d, la densité asymptotique mu_a(d) des ensembles d'entiers n tels que s_2(n+a)-s_2(n)=d. Pour tout a, mu_a est une mesure de probabilité sur Z. On démontre que pour toute mesure invariante ergodique sur {0,1}^N, et pour toute suite d'entiers (a_n) dont les décompositions en binaire décrivent les préfixes d'un point générique de cette mesure, mu_{a_n} vérifie un théorème de type limite centrée. Ce résultat est obtenu en calculant les moments de mu_{a_n} qui sont donnés par des produits de matrices aléatoires. Une session false beliefs est envisageable par la suite ! Note: le programme complet du séminaire se trouve sur la page http://lipn.univ-paris13.fr/~banderier/Seminaires/ À demain, Thierry

1 0