Paper at POPL 2023

The paper entitled “A Calculus for Amortized Expected Runtimes” by Kevin Batz, Benjamin Kaminski (Saarland/UCL), Joost-Pieter Katoen, Christoph Matheja (DTU Lyngby) and Lena Verscht has been accepted for presentation at the 50th ACM Symposium on Principles of Programming Languages (POPL). The paper presents a weakest precondition-style calculus to determine the amortized expected run-time of randomized algorithms that manipulate dynamic data structures such as trees and lists.