Termination Analysis of Probabilistic Programs

Speaker:   Dr. Amir GOHARSHADY
           Assistant Professor
           Dept. of Computer Science and Engineering
           Dept.of Mathematics
           HKUST

Title: "Termination Analysis of Probabilistic Programs"

Date: Monday, 11 April 2022

Time: 3:00pm - 4:00pm

Zoom link:
https://hkust.zoom.us/j/928308079?pwd=MW9wTCtlSDd2MnViZGdNd2oreUpXZz09

Meeting ID:     928 308 079
Passcode:       20212022

Abstract:

Termination is one of the most classical undecidable problems in all of
computer science, going all the way back to Turing's study of the halting
problem. Despite its undecidability, it has a central role in formal
program verification and a rich body of theory and practical algorithms
have been developed over the decades to handle the special decidable cases
of this classical problem. In this talk, we first review some of the most
prominent and standard ways of proving termination for non-probabilistic
programs. We then turn our focus on extending these methods to the much
more intricate (and interesting) case of probabilistic programs. We also
spend some time on examples showing how and why our intuition fails us
when we deal with infinite probability spaces in the context of program
analysis.


****************
Biograpgy:

Amir Goharshady is an Assistant Professor of CSE and MATH at HKUST. His
research is in mathematical and algorithmic aspects of program
verification and formal methods. On any given day, Amir is likely working
on parameterized algorithms, probabilistic programs, or verification of
blockchain protocols. He did his PhD at the Institute of Science and
Technology Austria (IST Austria) and has been a recipient of various
research awards, including fellowships from Facebook, IBM, the Austrian
Academy of Sciences, and the Royal Commission for the Exhibition of 1851,
as well as the Best PhD Dissertation Award of the European Association for
Programming Languages and Systems (EAPLS), IST Austria's Best PhD
Dissertation Award, two IEEE Computer Society Lance Stafford Larson Best
Paper Awards and the Iranian Presidential Research Award (Khwarizmi
Prize).

Right after this talk, Amir will be teaching COMP 4901W: Introduction to
Blockchain, Cryptocurrencies and Smart Contracts.