[TYPES/announce] webinar by Martin Avanzini as part of SCOT seminar: On Continuation-Passing Transformations and Expected Cost Analysis : Nov 9th 2021, 3pm-4pm (CET)

[Patrick Baillot]

Dear colleagues,

  The next talk of the Semantic and Formal Approaches to Complexity (SCOT) webinar will be given by Martin Avanzini. Abstract and practical informations are given below. You are welcome to attend it on Zoom. To obtain the connexion informations and/or be informed of future talks, please subscribe to the mailing list (for that send an email with subject "subscribe scot_webinar" and empty body to sympa at groupes.renater.fr).

Tuesday November 9th 2021, 3pm-4pm (CET). Martin Avanzini (Inria Sophia-Antipolis).

  Title:  On Continuation-Passing Transformations and Expected Cost Analysis

- the room will open at 2:45pm (CET). You can come with your coffee for a chat!

- the talk will start at 3:00 pm.


Abstract:
In this talk I will present recent joint work with Ugo Dal Lago and Gilles Barthe, which is concerned with a novel methodology for the cost analysis of randomized higher-order programs, i.e., programs which can sample values from chosen distributions during execution, and at the same time are capable of treating functions as first-class citizens. The evaluation of such a program results in a distribution of values, and has an expected cost, namely the average cost the program experiences along its execution.

The way we tackle such an expected cost analysis is reminiscent of the seminal work of Rosendahl (1989), and lies in turning the program at hand into a second one, which is structurally quite similar but computes the cost of execution in addition. This turns an intensional property, namely the cost of execution, into an extensional one. A crucial aspect of this program transformation is that probabilistic effects are eliminated along the way, thereby enabling classical reasoning tools for non-probabilistic programs in our context. As one such tool we propose a slight variation of a standard higher-order logic, dubbed EHOL, which we also use to study some classical examples from probability theory.
    
For the seminar:

Isabel Oitavem, Patrick Baillot, Ugo Dal Lago
------------------------
Seminar web page: https://urldefense.com/v3/__http://www.cs.unibo.it/*dallago/SCOSEM/__;fg!!IBzWLUs!DvCcv9xBlTNQDMTDnBnfuQYSIT2PKXmhE8cOyFWYey0MSJu1z2FuTi1GHAna8Zdoe4JePztdSF0wyQ$ 
The list's homepage: https://urldefense.com/v3/__https://groupes.renater.fr/sympa/info/scot_webinar__;!!IBzWLUs!DvCcv9xBlTNQDMTDnBnfuQYSIT2PKXmhE8cOyFWYey0MSJu1z2FuTi1GHAna8Zdoe4JePzuEyIZDzQ$ 
General information  about mailing lists: https://urldefense.com/v3/__https://groupes.renater.fr/sympa/help/introduction__;!!IBzWLUs!DvCcv9xBlTNQDMTDnBnfuQYSIT2PKXmhE8cOyFWYey0MSJu1z2FuTi1GHAna8Zdoe4JePzuhkLhmtA$ 
To unsubscribe from this list: send an email with subject "unsubscribe scot_webinar" and empty body to sympa at groupes.renater.fr
If you wish to subscribe: same procedure with subject "subscribe scot_webinar"