Mon 24 Jun 2019 14:20 - 14:40 at 224AB - Probabilistic Programming Chair(s): Martin Hirzel

We consider the problem of expected cost analysis over nondeterministic probabilistic programs,
which aims at automated methods for analyzing the resource-usage of such programs.
Previous approaches for this problem could only handle nonnegative bounded costs.
However, in many scenarios, such as queuing networks or analysis of cryptocurrency protocols,
both positive and negative costs are necessary and the costs are unbounded as well.

In this work, we present a sound and efficient approach to obtain polynomial bounds on the
expected accumulated cost of nondeterministic probabilistic programs.
Our approach can handle (a) general positive and negative costs with bounded updates in
variables; and (b) nonnegative costs with general updates to variables.
We show that several natural examples which could not be
handled by previous approaches are captured in our framework.

Moreover, our approach leads to an efficient polynomial-time algorithm, while no
previous approach for cost analysis of probabilistic programs could guarantee polynomial runtime.
Finally, we show the effectiveness of our approach using experimental results on a variety of programs for which we efficiently synthesize tight resource-usage bounds.

Mon 24 Jun
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

14:00 - 15:30: PLDI Research Papers - Probabilistic Programming at 224AB
Chair(s): Martin HirzelIBM Research
pldi-2019-papers14:00 - 14:20
Steffen SmolkaCornell University, Praveen KumarCornell University, David M. KahnCarnegie Mellon University, USA, Nate FosterCornell University, Justin HsuUniversity of Wisconsin-Madison, USA, Dexter KozenCornell University, Alexandra SilvaUniversity College London
DOI Pre-print Media Attached
pldi-2019-papers14:20 - 14:40
Peixin WangShanghai Jiao Tong University, Hongfei FuIST Austria, Amir Kafshdar GoharshadyIST Austria, Krishnendu ChatterjeeIST Austria, Xudong QinEast China Normal University, China, Wenjun ShiEast China Normal University, China
Media Attached
pldi-2019-papers14:40 - 15:00
Marco Cusumano-TownerMIT-CSAIL, Feras SaadMassachusetts Institute of Technology, Alexander K. LewMassachusetts Institute of Technology, USA, Vikash MansinghkaMIT
Media Attached
pldi-2019-papers15:00 - 15:20
Jieyuan ZhangUNSW, Australia, Jingling XueUNSW Sydney
Media Attached