Computer Science Thesis Proposal

Wednesday, September 29, 2021 - 10:00am to 11:30am


Virtual Presentation - ET Remote Access - Zoom


DI WANG, Ph.D. Student

Static Analysis of Probabilistic Programs: An Algebraic Approach

Probabilistic programs are programs that can draw random samples from probability distributions and involve random control flows. They are becoming increasingly popular and have been applied in algorithm design, cryptographic protocols, uncertainty modeling, and statistical inference. Formal reasoning about probabilistic programs comes with unique challenges, because it is usually not tractable to obtain the exact result distributions of probabilistic programs. This thesis focuses on an algebraic approach for static analysis of probabilistic programs. The thesis first provides a brief background on measure theory and introduces an imperative arithmetic probabilistic programming language APPL with a novel hyper-graph program model. Second, the thesis presents an algebraic denotational semantics for APPL with a new model of nondeterminism that involves nondeterminacy among state transformers. The thesis then proposes a general algebraic framework PMAF for designing, implementing, and proving the correctness of static analyses of probabilistic programs. The thesis also includes a concrete static analysis: central-moment analysis for cost accumulators in probabilistic programs. As proposed work, I plan to (i) enhance the implementation for central-moment analysis, and (ii) instantiate the analysis framework PMAF for central-moment reasoning. Furthermore, I will investigate static-analysis techniques for programs used for probabilistic inference to help improve efficiency and detect bugs.

Thesis Committee:
Jan Hoffmann (Chair)
Matt Fredrikson
Stephen Brookes
Thomas Reps (University of Wisconsin-Madison)
Hongfei Fu (Shanghai Jiao Tong University)

Additional Information

Zoom Participation. See announcement.

For More Information, Contact:


Thesis Proposal