Title: Perturbation analysis in probabilistic verification

Speaker: Taolue Chen, Birkbeck, University of London, UK

Time: 3:00 pm, April 9th (Monday), 2018

Venue: Lecture room (Room 334), Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

 

Abstract: Perturbation analysis in probabilistic verification addresses the robustness and sensitivity problem for verification of stochastic models against qualitative and quantitative properties. In this talk, I will present a general framework to carry out such an analysis. In particular, we identify two types of perturbation bounds, namely non-asymptotic bounds and asymptotic bounds. Non-asymptotic bounds are exact, pointwise bounds that quantify the upper and lower bounds of the verification result subject to a given perturbation of the model, whereas asymptotic bounds are closed-form bounds that approximate non-asymptotic bounds by assuming that the given perturbation is sufficiently small. I will mainly demonstrate the perturbation analysis for Discrete-time Markov Chains, focusing on the computational aspect, namely, the algorithms and tight complexity bounds for calculating both non-asymptotic bounds and asymptotic bounds. I will also discuss some other work related to perturbation analysis briefly.

Bio: Taolue Chen received the Bachelor’s and Master’s degrees from the Nanjing University, China, both in computer science. He was a junior researcher (OiO) at the CWI and acquired the PhD degree from the Free University Amsterdam, The Netherlands. He is currently a lecturer at the Department of Computer Science and Information System, Birkbeck, University of London, United Kingdom. Before this post, he was a lecturer at Middlesex University, a research assistant at the University of Oxford, and a postdoctoral researcher at the University of Twente. His research interests include quantitative analysis and synthesis of computer programs and systems, machine learning and data science, algorithms and computational complexity. More information can be found at http://www.dcs.bbk.ac.uk/~taolue/.