### Séminaire des doctorants

Séminaire dans lequel les doctorant.e.s et les stagiaires présentent leur travaux devant une audience moins intimidante puisqu'elle est composée des autres doctorant.e.s, stagiaires et éventuellement post-docs.

** Date et lieu :** le mercredi à 11h, Sophie Germain

** Responsables :** Laurent Feuilloley, Nicolas Jeannerod, Théo Zimmermann

Voir aussi le blog du séminaire, avec des résumés de certains exposés, à l'adresse : https://semidoc.github.io/.

Mercredi 03 mai 2017 · 11h00 · Salle 3052

Alexandre Nolin · Quantum, a look through nonlocality

Mercredi 19 avril 2017 · 11h00 · Salle 3052

Pierre Cagne (PPS team) · Lawvere’s hyperdoctrines and notions of equality

Mercredi 05 avril 2017 · 11h00 · Salle 3052

Guillaume Lagarde (Automata and applications Group) · On the stability of the Lempel-Ziv compression algorithm

The presentation will just use basic combinatorics.

Mercredi 22 mars 2017 · 11h00 · Salle 3052

Gabriel Radanne (PPS team) · GADTs gone mild

Since their adoption in “mainstream” languages, GADTs have been known for allowing to elegantly write toy typed interpreter at the cost of horrible type error messages and numerous headaches. Or, as Yaron Misky said, “I assumed that it was the kind of nonsense you get when you let compiler writers design your programming language.”.

In this talk, I will present GADTs, what they are, and what useful things we can do with them. This will take us on quite a journey, with some traces of C, a pinch of memory layout, a cameo from pushdown automata and a healthy amount of Prolog. The only requirements will be a passing familiarity with OCaml and the caffeinated beverage of your choice.

Mercredi 08 mars 2017 · 11h00 · Salle 3052

Pablo Eduardo Rotondo (Automata and applications Group) · Continued Fractions and the Recurrence of Sturmian Words

Mercredi 22 février 2017 · 11h00 · Salle 3052

Lucas Boczkowski (Algorithms and complexity Group) · Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits

This paper considers the basic PULL model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify the smallest amount of information revealed in each interaction (message size) that nevertheless allows for efficient and robust computations of fundamental information dissemination tasks. We focus on the Majority Bit Dissemination problem that considers a population of n agents, with a designated subset of source agents. Each source agent holds an input bit and each agent holds an output bit. The goal is to let all agents converge their output bits on the most frequent input bit of the sources (the majority bit). Note that the particular case of a single source agent corresponds to the classical problem of Broadcast (also termed Rumor Spreading). We concentrate on the severe fault-tolerant context of self-stabilization, in which a correct configuration must be reached eventually, despite all agents starting the execution with arbitrary initial states. In particular, the specification of who is a source and what is its initial input bit may be set by an adversary.

We first design a general compiler which can essentially transform any self-stabilizing algorithm with a certain property (called “the bitwise-independence property”) that uses l-bits messages to one that uses only (log l)-bits messages, while paying only a small penalty in the running time. By applying this compiler recursively we then obtain a self-stabilizing Clock Synchronization protocol, in which agents synchronize their clocks modulo some given integer T, within O(log n log T) rounds w.h.p., and using messages that contain 3 bits only. We then employ the new Clock Synchronization tool to obtain a self-stabilizing majority broadcast protocol which converges in O(log n) time, w.h.p., on every initial configuration, provided that the ratio of sources supporting the minority opinion is bounded away from half. Moreover, this protocol also uses only 3 bits per interaction.

Based on joint work with A. Korman and E. Natale.

Mercredi 25 janvier 2017 · 11h00 · Salle 3052

Thibaut Girka (PPS team) · Oracle-based Differential Operational Semantics (or Explaining program differences with programs)

We illustrate this framework by instantiating it on a toy imperative language and by presenting several /difference languages/ ranging from trivial equivalence-preserving syntactic transformations to characterized semantic differences. Through those examples, we will present the basis of our framework, show how to use it to relate syntactic changes with their effect on semantics, how one can abstract away from the small-step semantics presentation, and discuss the composability of oracles.

Mercredi 11 janvier 2017 · 11h00 · Salle 3052

Fabian Reiter (Automata and applications Group) · Asynchronous Distributed Automata

** Voir les archives sur l'ancien site web :** http://www.pps.univ-paris-diderot.fr/~c.jacq/seminaire-thesards