Seminar


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

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