Petr's photo

Petr Novotný

Assistant professor in computer science
I work as an assistant professor at the Faculty of Informatics, Masaryk University, Brno, Czech Republic. Previously, I was an ISTFellow postdoc at IST Austria, working in the group of Krishnendu Chatterjee. My chief research interests are analysis of probabilistic programs, application of formal methods in AI, and theoretical foundations of probabilistic verification.

I am looking for motivated student collaborators! Funded positions for both undergraduates and Ph.D. candidates are available. The collaboration will be focused on probabilistic programs, their analysis, and the use of probabilistic programming in AI. Look here or contact me for further info.
You can download my full academic CV here (version from August 2018).

What's new

December 2018 My research on analysis of probabilistic received funding from the Czech Science Foundation! From January 2019, I will act as the principal investigator for the grant project "Verification and Analysis of Probabilistic Programs."
September 2018 Giving an invited talk on Risk-Aware Planning in Partially Observable Markov Decision Processes at the GAMENET conference (a meeting of the COST Action European Network for Game Theory) in Krakow.
July 2018 Check out our new complexity results on finite-horizon MDPs, a collaboration with N. Balaji, S. Kiefer, G.A. Pérez, and M. Shirmohammadi. Feedback is welcome.
July 2018 Presenting at IJCAI'18. Check out the paper here.
May 2018 Our paper Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-sum Objectives was accepted for publication at IJCAI-ECAI'18!


Faculty of Informatics, Masaryk University
Botanická 68a
60200 Brno
Czech Republic

e-mail: (remove XYZ) petr.novotnyXYZ {at}
See also my DBLP and Google Scholar profiles.

    Conference Papers

  1. Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-sum Objectives.
    K. Chatterjee, A. Elgyütt, P. Novotný, and O. Rouillé.
    IJCAI-ECAI 2018. [tech. report]
  2. Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS.
    T. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, D. Velan, F. Zuleger.
    LICS 2018. [tech. report]
  3. Lexicographic Ranking Supermartingales: An Efficient Approach to Termination of Probabilistic Programs.
    S. Agrawal, K. Chatterjee, and P. Novotný.
    POPL 2018. [paper, tech. report]
  4. Optimizing Expectation with Guarantees in POMDPs.
    K. Chatterjee, P. Novotný, G. A. Pérez, J.-F. Raskin, and Đ. Žikelić.
    AAAI 2017 [paper, tech. report]
  5. Stochastic Invariants for Probabilistic Termination.
    K. Chatterjee, P. Novotný, and Đ. Žikelić.
    POPL 2017. [paper, tech. report]
  6. Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs.
    K. Chatterjee, H. Fu, P. Novotný, and R. Hasheminezhad.
    POPL 2016. [paper, tech. report]
  7. Stochastic Shortest Path with Energy Constraints in POMDPs: (Extended Abstract).
    T. Brázdil, K. Chatterjee, M. Chmelík, A. Gupta, and P. Novotný.
    AAMAS 2016. [paper, tech. report]
  8. Optimizing the Expected Mean Payoff in Energy Markov Decision Processes.
    T. Brázdil, A. Kučera, and P. Novotný.
    ATVA 2016. [paper, tech. report]
  9. Stability in Graphs and Games.
    T. Brázdil, V. Forejt, A. Kučera, and P. Novotný.
    CONCUR 2016. [paper, tech. report]
  10. Long-Run Average Behaviour of Probabilistic Vector Addition Systems.
    T. Brázdil, S. Kiefer, A. Kučera, and P. Novotný.
    LICS 2015. [paper, tech. report]
  11. Optimizing Performance of Continuous-Time Stochastic Systems Using Timeout Synthesis.
    T. Brázdil, L. Korenčiak, J. Krčál, P. Novotný, and V. Řehák.
    QEST 2015. [paper, tech. report]
  12. Minimizing Running Costs in Consumption Systems.
    T. Brázdil, D. Klaška, A. Kučera, and P. Novotný.
    CAV 2014. [paper, tech. report]
  13. Zero-Reachability in Probabilistic Multi-Counter Automata.
    T. Brázdil, S. Kiefer, A. Kučera, P. Novotný, and J.-P. Katoen.
    CSL-LICS 2014. [paper, tech. report]
  14. Solvency Markov Decision Processes with Interest.
    T. Brázdil, T. Chen, V. Forejt, P. Novotný, and A. Simaitis.
    FSTTCS 2013. [paper, tech. report]
  15. Determinacy in Stochastic Games with Unbounded Payoff Functions.
    T. Brázdil, A. Kučera, and P. Novotný.
    MEMICS 2012. [paper, tech. report] Best paper award
  16. Efficient Controller Synthesis for Consumption Games with Multiple Resource Types.
    T. Brázdil, K. Chatterjee, A. Kučera, and P. Novotný.
    CAV 2012. [paper, tech. report]
  17. Minimizing Expected Termination Time in One-Counter Markov Decision Processes.
    T. Brázdil, A. Kučera, P. Novotný, and D. Wojtczak.
    ICALP 2012. [paper, tech. report]
  18. Technical Reports

  19. Efficient Algorithms for Checking Fast Termination in VASS.
    T. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, and D. Velan.
    [tech. report]

Autumn 2018

Office hours: Tuesday 16:00-17:30, C412 (during the term)

Courses: Tutorials:

Ph.D. Positions

I offer a funded Ph.D. candidate position in the area of program analysis and probabilistic verification. An official call is coming soon via the university website, but if you're interested, you are encouraged to get in touch with me beforehand, enclosing your CV and a statement of motivation. A transcript of your study records and letters of recommendation will be requested at a later stage.

Research Engagement for Bachelor's and Master' Students

I am looking for motivated student collaborators! Would you like to dig deeper into some of the modern topics in computer science? Do you enjoy learning new things? Would you like to try to contribute to the body of scientific knowledge? If yes, then read on!

My research focuses on verification and analysis of systems that exhibit probabilistic behaviour. Such systems prominently appear particularly in the field of artificial intelligence (AI), but also in other domains, such as privacy & security, operations research, and bio-informatics.

There is a wide range of student research opportunities within this field. Maybe you could be interested in an implementation work, where your task would be to write a prototype tool based on our research and experimentally evaluate it on suitable benchmarks. Or, on the other side of the spectrum, you might enjoy to do mathematics and prove theorems. Both of these types of projects are available within my research, as well as combinations thereof. No previous research experience is necessary: diligence and willingness to learn new things are crucial.

There are several ways of joining my research. First, you can have a look at the Bachelor's and Master's thesis topics below. Those that are directly related to some of my ongoing research projects are marked by an asterisk (*). Second, if you do not find exactly the topic that would suit you or you would like to explore further possibilities, just get in touch with me and we can discuss suitable topics.

Last but not least, funding is available for participants on my research project "Verification and Analysis of Probabilistic Programs." In addition, depending on the precise topic there is a possibility of short-term research internships at select institutions (IST Austria, UT Austin,...).

Bachelor's and Master's Thesis Projects

A list of thesis topics that I currently offer can be found below or in the university information system. Most of the topics allow for scaling to both Bachelor's and Master's levels. The thesis language is negotiable (Czech, Slovak, English).

The list is not meant to be exhaustive — I am open to discussing other project ideas related to these topics or to my general research interests.

If you are interested in doing a thesis under my supervision, let me know; I'll be happy to answer your questions and clarify the details.

Links to particular topics: