2015


Retour à la vue des calendrier
Mardi 3 Novembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Colored triangulations of arbitrary dimensions are stuffed Walsh maps
Description: Luca Lionni
Mardi 10 Novembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: The Flajolet-Soria formula, Furstenberg and Christol's theorems
Description: Yining Hu
Mardi 17 Novembre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Identités de Gallai chromatiques opérant sur la fonction Theta Lovasz
Description: Denis Cornaz Un paramètre de graphe (une fonction qui associe un entier à tout graphe) est dit sandwich si, pour tout graphe, il est compris entre la taille de la clique maximum et le nombre chromatique.
Nous définissons à l'aide d'un graphe auxiliaire (un sous-graphe partiel du line-graphe) un opérateur PHI qui transforme tout paramètre sandwich en un autre paramètre sandwich.
Nous montrons que PHI améliore la qualité des bornes polynomiales pour la coloration (bornes obtenues par la programmation semie-définie), de plus, expérimentalement, l'amélioration est significative. Par ailleurs, PHI détériore la qualité de la borne obtenue par la programmation linéaire.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A computer-algebra-based formal proof of the irrationality of ?(3)
Description: Frédéric Chyzak We report on the formal verification of an irrationality proof of theevaluation at 3 of the Riemann zeta function. This verification usesthe Coq proof assistant in conjunction with algorithmic calculationsin Maple. This irrationality result was first proved by Apéry in1978, and our formalization follows the proof path of his originalpresentation. The crux of it is to establish that some sequencessatisfy a common recurrence. We formally prove this by an aposteriori verification of calculations performed by a Maplesession. This bases on computer-algebra algorithms implementingZeilberger's approach of creative telescoping. This experienceillustrates the limits of the belief that creative telescoping candiscover recurrences for holonomic sequences that are easily checked aposteriori. We discuss this observation and describe the protocol wedevised in order to produce complete formal proofs of the recurrences.Beside establishing the recurrences, our proof combines theformalization of arithmetical ingredients and of some asymptoticanalysis.Joint work with Assia Mahboubi, Thomas Sibut-Pinote, and Enrico Tassi.
Mercredi 18 Novembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: (Colloquium : Les mercredis du LIPN)
Description: Hsien-Kuei Hwang
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Coin Tossing in algorithmics (Colloquium : Les mercredis du LIPN)
Description: Hsien-Kuei Hwang Coin-tossing is one of the simplest ways of resolving a conflict, deciding between two alternatives, and generating random phenomena. It has been widely adopted in many daily-life situations and scientific disciplines. In this talk, I will present a few research themes connected to the use of coin-tossing in algorithmics, taken from my research: these include random permutations, data structures, evolutionary algorithms and leader selection. The main focus will be on the stochastic behaviors and the methods of analysis.
Heure: 15:00 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Coin-tossing in algorithmics
Description: Hsien-Kuei Hwang Coin-tossing is one of the simplest ways of resolving a conflict, deciding between two alternatives, and generating random phenomena. It has been widely adopted in many daily-life situations and scientific disciplines. In this talk, I will present a few research themes connected to the use of coin-tossing in algorithmics, taken from my research: these include random permutations, data structures, evolutionary algorithms and leader selection. The main focus will be on the stochastic behaviors and the methods of analysis.
Vendredi 20 Novembre
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: The Y=Y(SI) problem
Description: Andrew Polonsky We discuss an important problem in untyped lambda calculus. Put forward by
Statman, it asks whether there exists a fixed point combinator Y such that
Y=Ydelta, where delta = SI = yx.x(yx). It is conjectured that there is no such
Y.

After basic introduction and examples, we will show how Statman's conjecture
naturally generalizes in two directions.

In the first perspective, we investigate general conditions on terms G1,..,GN
which are fpc generators: for all terms M, M fpc => M G1 .. GN fpc

In the second direction, we look at the simply-typed Y-calculus, in which a
"formal" fpc is introduced together with the rewrite rule Yx –> x(Yx) Given
an arbitrary fpc Y, there is an obvious interpretation of this calculus in the
untyped lambda calculus. The Y=Y(SI) conjecture is reduced to the
conservativity of this interpretation, for any Y.
Vendredi 27 Novembre
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Interacting Hopf algebras: the theory of linear systems
Description: Fabio Zanasi We present by generators and equations the theory IH whose free model is the category of linear subspaces over a field k. Terms of IH are string diagrams which, for different choices of k, express different kinds of networks and graphical formalisms used by scientists in various fields, such as quantum circuits, electrical circuits and signal flow graphs. The equations of IH arise by distributive laws between PROPs of Hopf algebras – from which the name interacting Hopf algebras. The characterisation in terms of subspaces allows to think of IH as a string diagrammatic syntax for linear algebra: linear maps, spaces and their transformations are all faithfully represented in the graphical language, resulting in an alternative, often insightful perspective on the subject matter.

As main application, we use IH to axiomatise a formal semantics of signal processing circuits, for which we study full abstraction and realisability. Our analysis suggests a reflection about the role of causality in the semantics of computing devices.

This is a joint work with Filippo Bonchi and Pawel Sobocinski.
Mardi 1 Décembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: TBC
Description: Mark Ward
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: TBC
Description: Mark Ward
Mercredi 2 Décembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: An overview of an analytic approach for branching processes (Colloquium : Les mercredis du LIPN)
Description: Mark Ward One approach to solving some questions in probability theory--especially questions about asymptotic properties of algorithms anddata structures--is to take an analytic approach, i.e., to utilizecomplex-valued methods of attack. These methods are especially useful withseveral types of branching processes, leader election algorithms, patternmatching in trees, data compression, etc. This talk will focus on some ofthe highlights of this approach. I endeavor to keep it at a level that isaccessible for graduate students.
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: An Overview of an Analytic Approach for Branching Processes
Description: Mark Ward One approach to solving some questions in probability theory--especially questions about asymptotic properties of algorithms and data structures--is to take an analytic approach, i.e., to utilize complex-valued methods of attack. These methods are especially useful with several types of branching processes, leader election algorithms, pattern matching in trees, data compression, etc. This talk will focus on some of the highlights of this approach. I endeavor to keep it at a level that is accessible for graduate students.
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: An overview of an analytic approach for branching processes (Colloquium : Les mercredis du LIPN)
Description: Mark Ward One approach to solving some questions in probability theory--especially questions about asymptotic properties of algorithms anddata structures--is to take an analytic approach, i.e., to utilizecomplex-valued methods of attack. These methods are especially useful withseveral types of branching processes, leader election algorithms, patternmatching in trees, data compression, etc. This talk will focus on some ofthe highlights of this approach. I endeavor to keep it at a level that isaccessible for graduate students.
Jeudi 3 Décembre
Heure: 10:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Long-range order in random 3-colorings of Z^d [10h-12h]
Description: Yinon Spinka Consider a random coloring of a bounded domain in Zd with the probability of each coloring F proportional to exp(-?*N(F)), where ?>0 is a parameter (representing the inverse temperature) and N(F) is the number of nea rest neighboring pairs colored by the same color. This is the anti-ferromagnetic 3-state Potts model of statistical physics, used to describe magnetic interactions in a spin system. The Kotecký conjecture is that in such a model, for d?3 and high enough ?, a sampled coloring will typically exhibit long-range order, placing the same color at most of either the even or odd vertices of the domain. We give the first rigorous proof of this fact for large d. This extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the case ?=infinity.No background in statistical physics will be assumed and all terms will be explained thoroughly.Joint work with Ohad Feldheim.
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Distributed nearest neighbour mean shift clustering
Description: Tarn Duong Data clustering is an important tool for extracting meaningful information from large data sets. Despite the popularity of k-means clustering, it possesses two important limitations as it (a) requires a prior choice of the number of clusters and (b) produces only ellipsoidal clusters. Mean shift clustering is a generalisation of k-means which overcomes these limitations by defining clusters via a gradient ascent search of the data density. Nearest neighbour approaches are well-suited to computing the gradient ascent for multivariate data as they adapt to the local data density. On the other hand, the data adaptivity of nearest neighbour mean shift (NNMS) involves a higher computational burden, in terms of execution time and memory than k-means, which has hindered the more widespread use of NN MS. Its computational burden can be reduced with approximate nearest neighbours via random scalar projections (Locality Sensitive Hashing, LSH). To illustrate the feasibility of Big Data Clustering beyond k-means, we implement NNMS-LSH on a distributed Spark Scala ecosystem for multivariate clustering and image segmentation.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Long-range order in random 3-colorings of Z^d [10h-12h]
Description: Yinon Spinka Consider a random coloring of a bounded domain in Zd with the probability of each coloring F proportional to exp(-?*N(F)), where ?>0 is a parameter (representing the inverse temperature) and N(F) is the number of nea rest neighboring pairs colored by the same color. This is the anti-ferromagnetic 3-state Potts model of statistical physics, used to describe magnetic interactions in a spin system. The Kotecký conjecture is that in such a model, for d?3 and high enough ?, a sampled coloring will typically exhibit long-range order, placing the same color at most of either the even or odd vertices of the domain. We give the first rigorous proof of this fact for large d. This extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the case ?=infinity.No background in statistical physics will be assumed and all terms will be explained thoroughly.Joint work with Ohad Feldheim.
Mardi 8 Décembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Colored triangulations of arbitrary dimensions are stuffed Walsh maps
Description: Luca Lionni Regular D-edge-colored graphs encode D-dimensional colored triangulations ofpseudo-manifolds. We study such families of edge-colored graphs built from afinite but arbitrary set of building blocks, which extend the notion ofp-angulations to arbitrary dimensions. I will introduce a bijection between anysuch family and some colored combinatorial maps which we call stuffed Walshmaps. Those maps generalize Walsh's representation of hypermaps as bipartitemaps, by replacing the vertices which correspond to hyperedges withnon-properly-edge-colored maps.We are interested in the number of bi-chromatic cycles of the initialedge-colored graphs because because they encode the curvature of thecorresponding triangulated pseudo-manifold. I will therefore present new toolsthat use the bijection in order to study the graphs which maximize the numberof bi-chromatic cycles at fixed number of vertices and provide examples wherethe corresponding stuffed Walsh maps can be completely characterized.
Heure: 15:00 - 18:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatoire analytique des graphes et hypergraphes
Description: Elie de Panafieu
Lundi 14 Décembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Remise du doctorat honoris causa à Christian Krattenthaler
Mardi 15 Décembre
Heure: 09:20 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Journée en l'honneur de Christian Krattenthaler
Heure: 09:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Journée en l'honneur de Christian Krattenthaler
Heure: 09:30 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Un théorème de factorisation pour le nombre des pavages en losanges d'un hexagone avec des trous triangulaires
Description: Christian Krattenthaler Je présenterai un curieux théorème de factorisation pour le nombre des pavages en losanges d'un hexagone avecsymétrie verticale et horizontale dont plusieurs troustriangulaires ont été enlevés le long de l'axe de symétrie horizontale. Je relierai ce théorème avec des autresthéorèmes de factorisation, et je discuterai quelques conséquences et questions ouvertes.Ce travail a été effectué en commun avec Mihai Ciucu."A factorisation theorem for the number of rhombus tilings of a hexagon with trianglar holes"I shall present a curious factorisation theorem for the number of rhombus tilings of a hexagon with vertical andhorizontal symmetry axis, with triangular holes along the latter axis. I shall set this theorem in relation withother factorisation theorems, and discuss some consequences and open questions.This is joint work with Mihai Ciucu.
Heure: 10:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Un théorème de factorisation pour le nombre des pavages en losanges d'un hexagone avec des trous triangulaires
Description: Christian Krattenthaler Je présenterai un curieux théorème de factorisation pour le nombre des pavages en losanges d'un hexagone avecsymétrie verticale et horizontale dont plusieurs troustriangulaires ont été enlevés le long de l'axe de symétrie horizontale. Je relierai ce théorème avec des autresthéorèmes de factorisation, et je discuterai quelques conséquences et questions ouvertes.Ce travail a été effectué en commun avec Mihai Ciucu."A factorisation theorem for the number of rhombus tilings of a hexagon with trianglar holes"I shall present a curious factorisation theorem for the number of rhombus tilings of a hexagon with vertical andhorizontal symmetry axis, with triangular holes along the latter axis. I shall set this theorem in relation withother factorisation theorems, and discuss some consequences and open questions.This is joint work with Mihai Ciucu.
Heure: 10:45 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Approximants de Padé et polyzêtas
Description: Tanguy Rivoal Peu de résultats sont connus sur la nature diophantienne des valeurs de la fonction zêta et de leurs généralisations, les polyzêtas. Une méthode générale pour parvenir à montrer l'irrationalité de tel ou tel nombre consiste à construire des approximationspolynomiales, dites de Padé, de séries entières, puis à spécialiser pour obtenir des approximations numériques de ces nombres. Je présenterai diverses constructions d'approximants de Padé dans le contexte des polyzêtas. Certaines proviennent de travaux en communavec Stéphane Fischler.
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: The hard life of an opinion mining tool: dealing with deceptive opinions and irony.
Description: Paolo Rosso With the increasing of social media, consumers rely more than ever on online reviews to make their decisions. A recent survey found that 87% of them have reinforced their decisions to purchase a product due to positive online reviews. At the same time 80% of consumers have changed their minds on the basis of negative information they found online. Therefore, online opinions play an important role for companies and there is an increasing trend to post fake reviews with the aim to sound authentic and deceive the consumers. The detection of deceptive opinions is a quite challenging problem and not only automatically (only 60% of humans discriminate between truthful and deceptive opinions with a certain degree of accuracy). In the first part of the talk I will give an overview of the state-of-thye-art approaches for detecting deceptive opinions. The second part of the talk is devoted to another issue that makes the life of a sentiment analysis tool quite difficult: detecting irony. In ironic opinions what is literally said is usually negated, and in absence of an explicit negation marker. This makes sentiment analysis quite challenging. Therefore, there is a growing interest from the research community in investigating the impact of irony on sentiment analysis and a task has been organized recently at SemEval in 2015 on sentiment analysis of figurative language in Twitter. In the talk I will describe how irony is employed in tweets and reviews and what are the recent state-of-the-art attempts for its automatic detection. Linguistic devices such as ambiguity, incongruity, unexpectedness and emotional contexts play an important role as triggers of irony. At the end I will also address the even more challenging fine-grained problem of discriminating between irony and sarcasm: e.g. If you find it hard to laugh at yourself, I would be happy to do it for you.
Heure: 11:45 - 14:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Polynômes symétriques et inégalités
Description: Bodo Lass Un théorème fondamental pour la théorie des égalités affirme que les polynômes symétriques élémentaires engendrent la sous-algèbre des polynômes symétriques, et sont algébriquement indépendants. Nous explorons l'utilité de ce résultat pour la théorie des inégalités.
Heure: 14:15 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Le CRT est la limite d'échelle de grandes dissections aléatoires
Description: Bénédicte Haas Une dissection du polygone régulier à n côtés est la graphe formé par le polygone et certaines de ses diagonales, avec la règle que deux diagonales ne peuvent se croiser qu'aux sommets du polygone. On s'intéresse ici au comportement asymptotiquement d'une dissectionuniformément distribuée dans l'ensemble des dissections du polygone à n côtés. Nous verrons que multipliée par n^(-1/2) cette dissection uniforme converge vers un multiple du CRT brownien. Ce résultat se généralise à des mesures attribuant des poids de Boltzmann auxdegrés des faces des dissections, lorsque ces poids décroissent suffisamment vite.Il s'agit d'un travail en collaboration avec Nicolas Curien et Igor Kortchemski.
Heure: 15:30 - 18:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Gog, Magog et Schützenberger
Description: Philippe Biane Les triangles Gog et Magog sont formés d'entiers positifs satisfaisant certaines inégalités. Ils apparaissent dans de nombreuses questions d'algèbre, de combinatoire, de théorie des représentations ou de physique statistique. Je parlerai d'une approche récente,reposant sur l'involution de Schützenberger, du problème de construire des bijections explicites entre ces objets.
Heure: 16:30 - 19:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Sur la forme limite de l'identité dans le tas de sable abélien
Description: Andrea Sportiello Le modèle du Tas de Sable Abélien décrit d'une façon élémentaire des processus de diffusion dans des réseaux. Des configurations de sable instables se stabilisent en des configurations stables, suite à une dynamique de avalanches. Malgré sa simplicité, ce modèleprésente des phenoménes surprenents. On peut ansi considérer des configurations instables très simples à décrire, sur des réseaux réguliers, et observer le résultat à la fin de l'avalanche : on verra apparaitre des formes fractales complexes.Une de ces configurations est l'identité récurrente, Id. Quand le graphe est une portion carrée, de taille L, du réseau carré. On a donc une suite Id(L) de configurations, qui, mises à l'échelle, semblent converger vers une forme limite fractale, qui fascine leschercheurs depuis longtemps.On vient d'obtenir une description complète de cette forme. Ce résultat fait apparaitre plusieurs surprises: tous les points de contact entre les morceaux qui forment le fractal ont des coordonnées (x,y) qui appartiennent au meme corps cubique. Par exemple, le bienconnu "carré bleu" qu'on trouve au milieu de la configuration est à une distance du bord de 0.58315637..., c'est à dire, la seule racine réelle de l'équation 2x^3+3x^2+x-2=0.
Jeudi 17 Décembre
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Clustering collaboratif guidé par la diversité
Description: Jérémie Sublime Le clustering collaboratif est un domaine émergeant dont le but est de permettre à plusieurs algorithmes d'échanger leurs informations afin d'améliorer leurs performances sur les données respectives auxquelles ils ont accès. La collaboration se déroule généralement en deux étapes, avec les algorithmes travaillant dans un premier temps sur leurs données de façons individuelles, puis échangeant leurs informations dans un second temps.
Ce type d'apprentissage possède de nombreuses applications : clustering multi-vue, clustering multi-échelle, multi-expert, ou multi-distribué, ou encore le transfert de connaissances.
La méthode proposée ici permet de résoudre un des problèmes majeurs du clustering collaboratif, à savoir l'échange d'informations entre algorithmes de clustering très différents et qui n'ont pas initialement été pensés pour cet objectif. Notre méthode permet ainsi à des algorithmes de différentes familles de travailler ensemble, et donne également la possibilité de pondérer l'influence de certains d'entre eux avec des critères tels que la qualité ou la diversité de leurs solutions.