We present an approach for automatic complexity analysis of integer programs, based on an alternating modular inference of upper runtime and size bounds for program parts. While our approach was originally developed for non-probabilistic programs, we show how we extended it to also infer upper bounds on the expected runtimes of probabilistic integer programs automatically.

Moreover, for the non-probabilistic case, we show how recent techniques to improve automated termination analysis of integer programs can be integrated into our approach for the inference of runtime bounds.

To evaluate its power, we implemented our approach in a new version of our tool KoAT. Part of the programme of the research training group UnRAVeL is a series of introductory lectures on the topics of "randomness" and "uncertainty" in UnRAVeL’s research thrusts: Algorithms and complexity, verification, logic and languages, and their application scenarios. The main aim is to

Dear all, this is a reminder for Jürgen Giesl's talk on Improving Automatic Complexity Analysis of Probabilistic and Non-Probabilistic Integer Programs <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Das-Graduiertenkolleg/Aktuelle-Veranstaltungen/~tazip/Ringvorlesung-/?lidx=1> taking place *today at 16:30* in room 5053.2 and on Zoom. Please find the details below. provide doctoral researchers as well as master students a broad overview of the subjects of UnRAVeL. Science undergoes continuous change and lives from the constant quest for novel and better results, which are presented at conferences and in journals. This year, 10 UnRAVeL professors will present some of their most recent research successes. Everyone interested, in particular doctoral researchers and master students, are invited to attend the UnRAVeL lecture series 2022 and engage in discussions with the researchers. The talks take place on Tuesdays, 16:30–18:00 in room 5053.2 in the ground floor of building E2. All events are hybrid. To join remotely, please use https://rwth.zoom.us/j/96003885007?pwd=aUczMVdVU0ZXVGtQUFpwQnJHQUFhUT09 / Meeting ID: 960 0388 5007 / Passcode: 273710 Please find a list of all upcoming talks on the UnRAVeL website <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Studium/~pzix/Ringvorlesung-Veranstaltung/?lidx=1> and below: * 03/05/2022 Jürgen Giesl: Improving Automatic Complexity Analysis of Probabilistic and Non-Probabilistic Integer Programs * 10/05/2022 Martin Grohe: Graph Representations Based on Homomorphisms * 17/05/2022 Christina Büsing: A Branch & Bound Algorithm for Robust Binary Optimization with Budget Uncertainty * 24/05/2022 Erika Ábrahám: The Challenge of Compositionality for Stochastic Hybrid Systems * 21/06/2022 Sebastian Trimpe: Uncertainty Bounds for Gaussian Process Regression with Applications to Safe Control and Learning * 28/06/2022 Britta Peis: Stackelberg Network Pricing Games * 05/07/2022 Gerhard Lakemeyer: Tractable Reasoning in First-Order Knowledge Bases We are looking forward to seeing many of you in the UnRAVeL survey lecture "What's New in UnRAVeL?". Best regards, Andreas Klinger, Birgit Willms, and Tim Seppelt Logo