Novembre 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.