2013


Retour à la vue des calendrier
Jeudi 2 Mai
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Méthodes combinatoires pour la gravité quantique
Description: Aristide Baratin Certaines approches à la gravité quantique reposent sur une construction combinatoire de l'intégrale fonctionnelle.Une question centrale dans ce contexte est de savoir comment incorporer, ou éventuellement retrouver dans un régime approprié, les symétries de la théorie classique (invariance par difféomorphismes).Je présenterai certains aspects mathématiques de ce problème, que j'examinerai sous deux angles complémentaires : le point de vue des invariants dits de "state sum", où les difféomorphismes de la variété sont remplacés par certaines opérations combinatoires sur des triangulations (mouvements de Pachner). le point de vue des modèles de matrices, où l'invariance par difféomorphismes est le résultat de la sommation sur une certaine classe de graphes associés à des triangulations.
Heure: 14:30 - 17:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Le modèle à 6 vertex généralisé et les polynômes de Macdonald
Description: Tiago Dinis de Fonseca Les polynômes symétriques jouent, depuis toujours, un rôle assezimportant en physique.Par exemple, il est connu que la « fonction génératrice » du modèle à 6vertex (remarquablement,ce modèle est en bijection avec les matrices à signes alternants) estun polynôme de Schur.Plus récemment, on a découvert, que la « fonction génératrice » d'unegénéralisation de cemodèle est aussi un polynôme symétrique, plus précisément, un polynômede Macdonald.
Mardi 14 Mai
Heure: 12:30 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Quelques résultats sur les codes identifiants
Description: Petru Valicov Un code identifiant d'un graphe est un sous-ensemble C de sommetsqui est à la fois dominant (tout sommet du graphe a un voisin dansC ou appartient à C) et séparant (tous les sommets ont unvoisinage distinct à l'intérieur de C). Dans cet exposé, nousfaisons un tour d'horizon de quelques résultats sur cette notion.Nous proposons une caractérisation des graphes qui ont le codeminimum de taille n-1, n étant l'ordre du graphe. Egalement nous nous intéressons à ce paramètre dans la classe des graphes adjoints. Si le temps le permet, nous parlerons de la complexité du problème dans différentes sous-classes des graphes parfaits.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorial Hopf algebraic description of the multiscale renormalization in quantum field theory
Description: Thomas Krajewski
Vendredi 17 Mai
Heure: 00:59 - 13:30
Lieu: Salle à fixer, Université de Villetaneuse
Résumé: Are partial orderings intrinsic to computations?
Description: Antonino Salibra Answering a question by Honsell and Plotkin, we show that there are two equations between lambda terms, the so-called subtractive equations, consistent with lambda calculus but not contemporaneously satisfied in any Scott continuous model. We also relate the subtractive equations to the open problem of the order-incompleteness of lambda calculus, by studying the connection between the notion of absolute unorderability in a specific point and a weaker notion of subtractivity, namely n-subtractivity, for partially ordered algebras. Finally we study the relation between n-subtractivity and relativized separation conditions in topological algebras, obtaining an incompleteness theorem for a general topological semantics of lambda calculus.
Mardi 21 Mai
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Une généralisation du théorème de Roth pour les progressions arithmétiques
Description: Jehanne Dousse Le théorème de Roth établit que pour tout a>0, il exite un entier N tel que tout sous-ensemble de {1,...,N} de cardinal au moins aN contient une progressionarithmétique de longueur 3 (un ensemble de la forme {x,x+r,x+2r} avec x et r des entiers non nuls). Plusieurs autres théorèmes importants de combinatoire additiveconcernent les progressions arithmétiques, comme le théorème de Szemeredi ou celui de Green-Tao.Après une introduction à la combinatoire additive, nous présenterons une généralisation du théorème de Roth aux "d-configurations" (ensembles de la forme {x_i+x_j+a|1
Mercredi 22 Mai
Heure: 00:59 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Game semantics and applications to compilation (1/3): Semantic foundations of heterogeneous compilation
Description: Dan Ghica This is an introductory, motivational and methodological talk in which I will describe my "Seamless Computing" research programme. By "seamless" I mean that programming languages for unconventional architectures (e.g. distributed, reconfigurable, heterogeneous) can still conform to the long-established principles of machine independence, recast in this new setting. I will talk about when and how such conventional languages (higher-order, imperative, concurrent) can be compiled in a seamless way, using ideas based on the Geometry of Interaction and on game semantics.
Jeudi 23 Mai
Heure: 09:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Yueyun Hu (LAGA), Axel Bacher (LIPN), Vladas Sidoravicius (Sao Paulo), Hugo Duminil-Copin (Genève), Guy Fayolle (INRIA)
Description: Journée Math-S
Vendredi 24 Mai
Heure: 00:59 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Game semantics and applications to compilation (2/3): Abstract machines for game semantics
Description: Dan Ghica We will examine new abstract machines for game semantics which correspond to networks of conventional computers, and which can be used as an intermediate representation for distributed compilation. This is achieved in two steps. First we introduce the HRAM, a Heap and Register Abstract Machine, an abstraction of a conventional computer, which can be structured into HRAM nets, an abstract point-to-point network model. HRAMs are multi-threaded and subsume communication by tokens (cf. IAM) or jumps (cf. JAM). Game Abstract Machines (GAM), are HRAMs with additional structure at the interface level, but no special operational capabilities. We show that GAMs cannot be naively composed, but composition must be mediated using special HRAM combinators. HRAMs are flexible enough to allow the representation of game models for languages with state (non-innocent games) or concurrency (non-alternating games). We illustrate the potential of this technique by implementing a toy distributed compiler for ICA, a higher-order programming language with shared state concurrency, thus significantly extending our previous distributed PCF compiler. We show that compilation is sound and memory-safe, i.e. no (distributed or local) garbage collection is necessary. [Joint work with Olle Fredriksson, to appear at LICS'13]
Vendredi 31 Mai
Heure: 00:59 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Game semantics and applications to compilation (3/3): A type system for hard real-time computation
Description: Dan Ghica We will examine a type system, suitable for higher-order functional programming languages with mutable state, which can automatically certify the timing of execution. The system is generally applicable to hard real-time computation and especially to the automatic synthesis of computational pipelines. We present the general typing rules, a categorical semantic model and a proof of coherence as well as a concrete programming language with a type inference algorithm and a concrete game-semantic model. [Joint work with Alex Smith]
Heure: 00:59 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: From Mind to Turing to Mind
Description: Henk Barendregt Based on introspection Alan Turing analyzed the process by which humans
perform  computations. Recent papers on consciousness go in the other
direction: this is seen as a hybrid Turing machine process. Hybrid in
the sense that it acts both discretely and in parallel, where the Turing
machine quadruplets are implemented by a neural net.

We also focus on mind-states and their possible implementations in the
brain, based on recent progress in neuroscience.

If the claims in the talk are validated one day, then this would be
emperical evidence for the Church-Turing thesis
Mardi 4 Juin
Heure: 00:59 - 15:00
Lieu: Amphithéâtre Euler, Institut Galilée, Université de Villetaneuse
Résumé: Exploring Scholarly Data with Rexplore
Description: Enrico Motta
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorics of the hard-squares model
Description: Andrew Rechnitzer
Vendredi 7 Juin
Heure: 00:59 - 14:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Graphical Foundations for Dialogue Games
Description: Cai Wingfield In 2007, Harmer, Hyland and Melliès gave a formal mathematical foundation for game semantics using a notion they called a schedule, a structure describing interleavings of plays in games. Their definition was combinatorial in nature, but researchers often draw pictures when describing schedules in practice. Moreover, several proofs of key properties, such as that the composition of schedules is associative, involve cumbersome combinatorial detail, whereas in terms of pictures the proofs are straightforward, reflecting the geometry of the plane. Here, we give a geometric formulation of schedules, prove that they are isomorphic to Harmer et al.'s definitions, and illustrate their value by giving such geometric proofs. Harmer et al.'s notions may be combined to describe plays in multi-component games, and researchers have similarly developed intuitive graphical representations of plays in these games. We give a characterisation of these diagrams and explicitly describe how they relate to the underlying schedules, finally using this relation to provide new, intuitive proofs of key categorical properties.
This is a joint work with Guy McCusker and John Power.
Mardi 11 Juin
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Extreme statistics of non-intersecting Brownian motions
Description: Grégory Schehr Non-intersecting Brownian motions (BMs) havebeen the subject of numerous studies both in mathematics and in physics. In addition to theirdeep connection with random matrix theory, It was shown that they are at the heart of manyfundamental models of statistical physics, like stochastic growth models or directed paths in random media. In this talk I will review some recent results which we have obtained for the extreme statistics,like the maximal height, of such non-intersecting BMs.    Les marcheurs Browniens conditionnés à ne pas se croiser ontsuscité beaucoup d'intérêt ces dernièresannées, tant en mathématique (pour leurs aspectsprobabilistes et combinatoires) qu'en physique (comme desmodèles de polymères ou de transition de mouillage ou defusion). Dans cet exposé je présenterai un calcul exact dela distribution de la hauteur maximale d'une collection de N pontsBrowniens (appelés 'watermelons without wall') et de Nexcursions Browniennes (appelées 'watermelons with awall') conditionnés à ne pas se croiser. Je montreraique dans la limite asymptotique où N tend vers l'infini cettedistribution converge vers la distribution de Tracy-Widom quidécrit les fluctuations de la plus grande valeur propre dematrices aléatoires de l'ensemble gaussien orthogonal (GOEpour 'Gaussian Orthogonal Ensemble'). Je discuterai enfin uneapplication de ces résultats asymptotiques à desmodèles de croissance stochastique.
Jeudi 13 Juin
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Journée ANR Magnum
Description: 10h30 Aline Parreau (LIFL) Une preuve combinatoire du lemme local de Lovasz11h45 Julien David (LIPN) & Yann Ponty (LIX) présentation de RDos (Random Discrete Objects Suite): un ensemble d'outils pour la génération aléatoire d'objets combinatoires 12h30 Buffet en salle A20114h Mathieu Raffinot (LIAFA) Nouvelles avancées dans la recherche de motifs uniques ou consécutifs dans des permutations travail en commun avec D.l Belazzougui (Univ. of Helsinki), A. Pierrot (LIAFA) et S. Vialette (LIGM) 15h15 Axel Bacher (LIPN) Génération aléatoire d'arbres en taille exacte et linéaire en temps et en espace 16h15 Discussion : bilan et perspectives après 30 mois
Vendredi 14 Juin
Heure: 00:59 - 14:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Some Results for Linear Logic Full Completeness
Description: Hugh Steele Many full completeness theorems have been established for fragments of
linear logic since the notion was first defined by Samson Abramsky and
Radha Jagadeesan in their 1992 paper. For the most part, these results
are obtained on a case-by-case basis: the subject of each proof is
precisely one category.

In this talk it is shown that the Hyland-Tan double glueing
construction can transform all tensor-generated compact closed
categories with finite biproducts into fully complete models of
unit-free MLL. The arguments employed are based around considering the
combinatorics behind the construction using standard linear algebra.
It is also discussed how another double glueing construction may be
able to create similar categories satisfying unit-free MALL full
completeness.
Mardi 18 Juin
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Where the really hard problems really are?
Description: Lenka Zdeborova
Lundi 1 Juillet
Heure: 00:59 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: After the f-score: applying parser output in sentiment analysis, grammatical error detection and quality estimation for machine translation
Description: Jennifer Foster several natural language processing applications, either because the "sense-making" applications such as sentiment analysis or question in "language proofing" applications such as grammar checking or experiments carried out in the National Centre for Language Technology parser output in three downstream applications, namely, sentiment translation. In all these experiments some kind of phrase structure used to parse the input, and in some cases, the phrase structures were structure trees and dependency graphs was employed in the downstream clear from these experiments that syntactic parsing always provides some syntactic information or what the relationship between the accuracy of F1 or labelled attachment accuracy) and its usefulness in the downstream 
Vendredi 5 Juillet
Heure: 00:59 - 14:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Forcing in classical realizability: the case study of Herbrand trees
Description: Lionel Rieg Krivine presented in 2010 a methodology to combine Cohen's forcing with
the theory of classical realizability and showed that the forcing
condition can be seen as a reference that is not subject to backtracks.
The underlying classical program transformation was then analyzed by
Miquel (2011) in a fully typed setting in classical higher-order
arithmetic (PAw+).As a case study of this methodology, I present a method to extract a
Herbrand tree from a classical realizer of an existential formula,
following the idea of the proof of Herbrand theorem.  Unlike the
traditional proof based on Konig's lemma (using a fixed enumeration of
atomic formulas), our method is based on the introduction of a
particular Cohen real.  It is formalized as a proof in PAw+, making
explicit the construction of generic sets in this framework in the
particular case where the set of forcing conditions is arithmetical.  We
then analyze the algorithmic content of this proof.
Mercredi 10 Juillet
Heure: 13:30 - 16:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Soutenance à mi-parcours
Description: Nguyen Hoang-Nghia
Heure: 14:30 - 17:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Soutenance à mi-parcours
Description: Ladji Kane
Heure: 15:30 - 18:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Soutenance à mi-parcours
Description: Alice Jacquot
Heure: 16:30 - 19:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Goûter de clôture
Vendredi 12 Juillet
Heure: 00:59 - 12:00
Lieu: Amphi Copernic, Institut Galilée, Université de Villetaneuse
Résumé: Bisimulations from graphical encodings (DPOs, RPOs, cospans, and all that)
Description: Fabio Gadducci The talk presents a personal recollection of recent results on the synthesis of labelled transition systems (LTSs) for process calculi.
The starting point is a visual technique for modelling the reduction semantics of nominal calculi: processes are mapped into graphs equipped with "interfaces", such that the denotation is fully abstract with respect to the structural congruence. The encoding allows for the reuse of standard graph rewriting theory and tools for simulating the reduction semantics of the calculus, such as the "double pushout" (DPO) approach and its concurrent semantics (which allows for the simultaneous execution of independent reductions)
Graphs with interfaces are just an instance of a cospan category (over the category of graphs). which is amenable to the synthesis mechanism based on "borrowed contexts" (BCs), proposed by Ehrig and Koenig, which are in turn an instance of "relative push outs" (RPOs), originally introduced by Milner and Leifer. The BC mechanism allows for the effective construction of an LTS that has graphs with interfaces as both states and labels, and such that the associated bisimilarity is automatically a congruence.
Since the category of cospans over graphs admits RPOs (as proved by Sassone and Sobocinski), its choice as the domain of the encoding for nominal calculi ensures that the synthesis of an LTS can be performed, and that a compositional observational equivalence is obtained. The talk discusses the LTS distilled by exploiting the encoding of CCS and Mobile Ambients processes.