## Special talks

#### Future talks

#### Past talks

Exposés hors-séries

jeudi 20 septembre 2018, 10h30, Amphi Turing (bâtiment Sophie Germain)

**Leonid Libkin** (University of Edinburgh) *Certain Answers Meet Zero-One Laws*

The talk will start with presenting a brief overview of querying incomplete information in databases and the main computational challenges it presents. Querying incomplete data invariably relies on the very coarse classification of query answers into those that are certain and those that are not. Such a classification is often very costly, and we propose to refine it by measuring how close an answer is to certainty.

This measure is defined as the probability that the query is true under a random interpretation of missing information in a database. Since there are infinitely many such interpretations, to pick one at random we adopt the approach used in the study of asymptotic properties and 0-1 laws for logical sentences and define the measure as the limit of a sequence. We show that in the standard model of missing data, the 0-1 law is observed: this limit always exists and can be only 0 or 1 for a very large class of queries. Thus, query answers are either almost certainly true, or almost certainly false, and this classification behaves very well computationally. When databases satisfy constraints, the measure is defined as the conditional probability of the query being true if the constraints are true. This can now be an arbitrary rational number, which is always computable. Another refinement of the notion of certainty views answers with a larger set of interpretations that make them true as better ones. We pinpoint the exact complexity of finding best answers for first-order queries.

Exposés hors-séries

jeudi 05 juillet 2018, 14h00, Salle 3052

**Laurent Viennot** (Inria Paris et IRIF) *Introduction to the blockchain*

The collaborative construction of a blockchain is the core of Bitcoin protocol for allowing various participants to agree on a list of valid transactions. The talk will be very informal, the intent is to give a very basic introduction on how Bitcoin works and highlight some of the scientific challenges behind it.

Exposés hors-séries

mardi 20 février 2018, 14h00, 3052

**Daniela Petrisan** (IRIF) *Up-To Techniques for Behavioural Metrics via Fibrations*

Up-to techniques are a well-known method for accelerating proofs of

behavioural equivalences between systems. In this talk, I introduce up-to techniques for behavioural metrics in a coalgebraic setting and provide general results that show under which conditions such up-to techniques are sound.

For a system modelled as a coalgebra for a certain functor, the behavioural distance can be seen as a coinductive predicate using a suitable lifting of the functor. I will focus on the so called Wasserstein lifting of a functor for which we provide a new characterization in a fibrational setting. This is useful for automatically proving the soundness of up-to techniques via a generic framework developed in a previous CSL-LICS'14 paper.

I will use fibrations of predicates and relations valued in a quantale, for which pseudo-metric spaces are an example. To illustrate our framework I provide an example on distances between regular languages.

Exposés hors-séries

jeudi 01 février 2018, 14h00, 3052

**Vincent Danos** (ENS) *Contractivity of Markov chains (metric couplings)*

The module is a continuation of the lecture series by Prakash Panangaden on Labelled Markov Processes, but can be independently followed.

Exposés hors-séries

mardi 30 janvier 2018, 14h00, 3052

**Vincent Danos** (ENS) *Bayesian inversion and approximation*

The module is a continuation of the lecture series by Prakash Panangaden on Labelled Markov Processes, but can be independently followed.

Exposés hors-séries

jeudi 25 janvier 2018, 14h00, 3052

**Prakash Panangaden** (McGill University) *Quantitative equational logic and free Kantorovich algebras*

Prakash will open his stay with a series of 4 introductory lectures on probabilistic systems: “Introduction to Labelled Markov Processes”

Exposés hors-séries

mardi 23 janvier 2018, 14h00, 3052

**Prakash Panangaden** (McGill University) *Metrics for LMPs*

Prakash will open his stay with a series of 4 introductory lectures on probabilistic systems: “Introduction to Labelled Markov Processes”

Exposés hors-séries

jeudi 18 janvier 2018, 14h00, 3052

**Prakash Panangaden** (McGill University) *A dual point of view: LMPs as function transformers*

Prakash will open his stay with a series of 4 introductory lectures on probabilistic systems: “Introduction to Labelled Markov Processes”

Exposés hors-séries

mardi 16 janvier 2018, 14h00, 3052

**Prakash Panangaden** (McGill University) *Introduction to LMPs: bisimulation, simulation, logical characterization*