Georg Zetzsche, head of the MPI-SWS Models of Computation group, has been awarded a 2022 ERC Starting Grant. Over the next five years, his project FINABIS will receive funding of 1.48 million euros for research on "Finite-state abstractions of infinite-state systems." Read more about the FINABIS project below.

In addition, MPI-SWS and University of Saarland alumnus Pramod Bhatotia, who is currently a professor at TU Munich, has also received a 2022 ERC Starting Grant for his project "DOS: A Decentralized Operating System".

ERC grants are the most prestigious and the most competitive European-level awards for ground-breaking scientific investigations. This year, less than 14% of all ERC Starting Grant applicants across all scientific disciplines received the award, with only 17 awardees in Computer Science across all of Europe and Israel!

These grants carry substantial research funding -- each winner receives up to 1.5 Million Euros over a period of 5 years to carry out their research. You can find more information about 2022 ERC Starting Grants here: https://erc.europa.eu/news-events/news/starting-grants-2022-call-results

The FINABIS Project

A fundamental question in computing is: What can programs find out algorithmically about other programs? If we want to analyze arbitrary programs, the answer is long known and simple: Essentially nothing. However, in recent decades, we have seen that if we restrict the class of analyzed programs, there is a rich variety of approaches to checking various important properties.

Understanding how to restrict the analyzed programs (while retaining as much expressivity as possible) has gained practical importance in the area of software verification. Here, algorithms for analyzing programs can be used to automatically check their correctness.

The available approaches to analyze programs typically transform a given program into an abstract model of computation. To account for program behaviors for all possible inputs, this usually results in models with infinitely many states. Designing algorithms that can work with such infinite-state systems poses a challenge. For example, we still do not have a clear picture of which types of infinite state spaces permit checking simple safety properties. In formal terms: For which infinite-state systems is reachability decidable?

In the FINABIS project ("Finite-state abstractions of infinite-state systems"), we are studying ways to transform infinite-state systems into finite-state systems that preserve some pertinent aspects of the original system. Understanding such transformations helps in two ways: First, finite-state systems are easier to work with algorithmically. So if our transformation preserves enough of the original system's behavior, we can simply analyze the finite system instead. Second, the specific transformations we study (subword closures and separability problems), and how we study them, are closely connected to understanding the decidability and complexity of reachability and also several other long-standing open problems in theoretical computer science.

The Max Planck Institutes in Computer Science invite applications for tenure-track faculty in all areas of computer science. We expect to fill several positions.

A doctoral degree in computer science or related areas and an outstanding research record are required. Successful candidates are expected to build a team and pursue a highly visible research agenda, both independently and in collaboration with other groups.

The institutes are part of a network of over 80 Max Planck Institutes, Germany's premier basic-research organisations. MPIs have an established record of world-class, foundational research in the sciences, technology, and the humanities. The institutes offer a unique environment that combines the best aspects of a university department and a research laboratory: Faculty enjoy full academic freedom, lead a team of doctoral students and postdocs, and have the opportunity to teach university courses; at the same time, they enjoy ongoing institutional funding in addition to third-party funds, a technical infrastructure unrivaled for an academic institution, as well as internationally competitive compensation.

We maintain an international and diverse work environment and seek applications from outstanding researchers worldwide. The working language is English; knowledge of the German language is not required for a successful career at the institutes.

Qualified candidates should apply on our application website (apply.cis.mpg.de). Review of applications will begin by December 1st, 2022.

The Max Planck Society wishes to increase the number of women in those areas where they are underrepresented. Women are therefore explicitly encouraged to apply. The Max Planck Society is also committed to increasing the number of employees with severe disabilities in its workforce. Applications from persons with severe disabilities are expressly desired.

The initial tenure-track appointment is for five years; it can be extended to seven years based on a positive midterm evaluation in the fourth year. A permanent contract can be awarded upon a successful tenure evaluation in the sixth year.

Ralf Jung, a doctoral student in the Foundations of Programming group, has accepted a position as a tenure-track assistant professor in the Department of Computer Science at ETH Zurich, Switzerland. Congratulations Ralf!

Ralf's primary research interest is in developing formal foundations and tools that establish machine-checked guarantees for real-world software systems. To achieve this, his work spans all the way from foundational and deeply theoretical to applied, from proving theorems to developing tools used by other researchers and software developers.. You can find out more about his work at https://research.ralfj.de/.

MPI-SWS doctoral student Simon Spies was awarded a 2022 Google PhD Fellowship to fund his doctoral research on Quiver, a verification tool for inferring functional correctness specifications in separation logic.

The Google PhD Fellowship Program was created to recognize outstanding graduate students doing exceptional and innovative research in areas relevant to computer science and related fields. Simon, who is advised by Derek Dreyer, was the only student in the area of Programming Technology and Software Engineering to receive a fellowship in 2022.

Link: https://research.google/outreach/phd-fellowship/

Mariya Toneva joins the tenure-track faculty at our institute starting September 2022. Mariya’s research is at the intersection of machine learning, natural language processing, and neuroscience. Her group bridges language in machines with language in the brain, with a focus on building computational models of language processing in the brain that can also improve natural language processing systems.

Prior to joining MPI-SWS, Mariya conducted research as a C.V. Starr Fellow at the Princeton Neuroscience Institute. She received her Ph.D. in a joint program between Machine Learning and Neural Computation from Carnegie Mellon University, and her B.S. in Computer Science and Cognitive Science from Yale University.

MPI-SWS Director Derek Dreyer has been selected as the program chair of the 51st ACM SIGPLAN Symposium on Principles of Programming (POPL'24), to be held in London January 17–19, 2024.

POPL is the premier venue in the area of programming languages and, alongside PLDI, ranks as one of the top two international conferences on this topic.

Principles of Programming Languages is the premier forum for the fundamental innovations in design, definition, analysis, transformation, and implementation of programming languages, programming systems, and programming abstractions.

MPI-SWS faculty member Rupak Majumdar has received the 2022 CONCUR Test-of-Time Award for his CONCUR 2003 paper on The Element of Surprise in Timed Games. The work was done in collaboration with Luca de Alfaro, Marco Faella, Thomas A. Henzinger, and Mariëlle Stoelinga.

The award citation reads as follows: "The paper studies concurrent two-player games played on timed game structures, and in particular the ones arising from playing on timed automata. A key contribution of the paper is the definition of an elegant timed game model, allowing both the representation of moves that can take the opponent by surprise as they are played "faster", and the definition of natural concepts of winning conditions for the two players -- ensuring that players can win only by playing according to a physically meaningful strategy. This approach provides a clean answer to the problem of time convergence, and the responsibility of the players in it. For this reason, it has since been the basis of numerous works on timed games. The algorithm established in the paper to study omega-regular conditions in this neat model of timed games is also enticing, resorting to mu-calculus on a cleverly enriched structure."

MPI-SWS faculty member Viktor Vafeiadis has received the 2022 Robin Milner Young Researcher Award, which is given by ACM SIGPLAN to recognize outstanding contributions by young investigators in the area of programming languages.  The award citation reads as follows:

"Viktor has become a world leader in semantics and verification research. His body of work includes fundamental and influential contributions to the study of concurrency, in particular separation logic and relaxed memory models. His landmark doctoral thesis developed RGSep, the first extension of concurrent separation logic to support formal proofs about fine-grained concurrent algorithms.  His work on Cave presented the first fully automatic verifier for establishing linearizability of a class of concurrent data structures, including ones with non-fixed linearization points. His work on CompCertTSO presented the first verified compiler for a concurrent language under a relaxed memory model. He developed the first direct (and mechanized) proof of soundness for concurrent separation logic (CSL) based on operational semantics—beautifully simple compared to prior proofs and a key enabler for proving soundness of more advanced program logics like CAP and Iris. He developed the first separation logic for the C/C++ relaxed memory model—a tour-de-force achievement compared to the standard CSL which assumes sequential consistency. This spawned a whole body of work on modular verification of concurrent data structures under relaxed memory models. His work has found and corrected a number of serious flaws in the C/C++ concurrency model, which led to changes in the C++ standard. And his "promising" semantics for relaxed-memory concurrency offered one of the first viable solutions to the 30-year-old "out-of-thin-air" problem and spawned much follow-on work. His work on GenMC presented the first efficient model checkers for relaxed-memory C/C++ programs with optimality guarantees about their state space exploration. Recent work together with his postdoc Azalea Raad (now faculty at Imperial), presented the first "persistency semantics" for non-volatile memory on multicore architectures. Viktor is not only highly-cited and incredibly prolific—he is also a true pioneer, repeatedly exploring dauntingly technical problems in the semantics and verification of concurrent programs before others dare to try."

This award makes MPI-SWS the only institution in the world to boast two recipients of the SIGPLAN Milner award among its faculty.

Two MPI-SWS faculty, Maria Christakis and Elissa Redmiles, have earned highly competitive Google Research Scholar awards. Maria Christakis's award was given for her research on metamorphic specification and testing of machine-learning models and Elissa Redmiles's award was given for her research on aligning technical data privacy protections with user concerns.

The Google Research Scholar Program provides unrestricted gifts of up to $60,000 to support research at institutions around the world and is focused on funding world-class research conducted by early-career professors. Award proposals go through an internal, merit-based review process and selected faculty can receive a Google Research Scholar award only once in their career. Award recipients are assigned a liaison at the company to share findings with and as a point of contact for further collaboration.

Derek Dreyer, head of the Foundations of Programming research group since 2008, has been appointed as a Scientific Member of the Max Planck Society and Scientific Director of MPI-SWS as of May 1, 2022.

Derek became known for his pioneering work in programming languages and verification, with a particular emphasis on building rigorous foundations for establishing the reliability and correctness of realistic software systems.  In recent years, he and his group have become especially well known for their work on the Iris and RustBelt verification frameworks, both implemented in the Coq proof assistant.  Developed initially in 2015, Iris is a system for developing and deploying higher-order concurrent separation logics; though only 7 years old, it has already been used in over 60 papers published in top venues in programming languages.  One of the most significant applications of Iris is RustBelt, which constitutes the first formal, machine-checked foundation for verifying the safety of the increasingly popular systems programming language Rust.  These large-scale verification efforts place Dreyer's group at the forefront of programming languages research worldwide.

Derek has received numerous accolades for his research, teaching, and service, including the 2017 ACM SIGPLAN Robin Milner Young Researcher Award, a 2015 ERC Consolidator Grant, multiple Distinguished Paper Awards at top conferences like POPL, PLDI, and OOPSLA, the OOPSLA'18 Distinguished Reviewer Award, and most recently, the "Busy Beaver Award" at Saarland University for outstanding commitment to teaching. Under his mentorship, members of his group have also received numerous awards, including the prestigious ACM SIGPLAN John C. Reynolds Doctoral Dissertation Award and ACM Doctoral Dissertation Honorable Mention Award (for Dr. Ralf Jung).

Derek was born in New York City in 1980.  He holds a Bachelor's in Mathematics and Computer Science from New York University and received his PhD in Computer Science from Carnegie Mellon University in 2005. From 2005 to 2007, he was a Research Assistant Professor at the Toyota Technological Institute at Chicago.  He joined MPI-SWS as a tenure-track faculty in January 2008, only a few years after the Institute's founding, and has been an integral member ever since. We are thus very proud to be able to retain him as a Scientific Director of the institute.

Sandra Kiefer has joined MPI-SWS as a research group leader, effective April 1, 2022. Her research interests include algorithmic and structural graph theory as well as logic in computer science, with a recent focus on the applicability of tools from these areas to the study of biochemical networks.

Sandra obtained her Ph.D. from RWTH Aachen University. For her work on combinatorial and logical approaches to graph comparison, she received the Ackermann Award 2020, the EACSL Outstanding Dissertation Award for Logic in Computer Science. After her Ph.D. studies, Sandra was a postdoctoral researcher at RWTH and at the University of Warsaw. She holds Bachelor’s degrees in Bioinformatics and Mathematics and a Master’s degree in Mathematics from Goethe University Frankfurt. She has also completed an M.Ed. degree in Mathematics and Spanish.

MPI-SWS researchers Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla have received an Outstanding Paper Award Honorable Mention at AAAI 2022, for their paper "Bayesian Persuasion in Sequential Decision-Making."

The AAAI conference is one of the leading international venues for AI research, covering all sub-areas of the field. AAAI 2022 received more than 9000 submissions, of which 1370 were accepted for publication. Of these 1370 papers, only three papers were selected for an outstanding paper award. Of these three outstanding papers, two were authored by researchers at the Saarland Informatics Campus.

MPI-SWS scientific director Joël Ouaknine was appointed as a Fellow by the Association for Computing Machinery (ACM), the largest computer science association in the world, Joel, who leads the “Foundations of Algorithmic Verification” research group, was appointed ACM fellow for his contributions to algorithmic analysis of dynamical systems.

ACM has also elected as Fellows two researchers from our neighboring Max Planck Institute for Informatics: Thomas Lengauer is recognized for contributions to bioinformatics and medical informatics and Bernt Schiele is recognized for contributions to large-scale object recognition, human detection, and pose estimation.

The ACM Fellows program recognizes the 1% of ACM members who have made the most outstanding achievements in the field of computer and information technology. Worldwide 71 new ACM Fellows were elected this year, twelve of them in Europe, four in Germany and three of them in Saarbrücken.

Further Information: 

• https://www.acm.org/media-center/2022/january/fellows-2021


• https://awards.acm.org/fellows/award-winners


• https://www.mpi-sws.org/people/joel/

Bob Harper, an MPI-SWS external scientific member, has received the 2021 ACM SIGPLAN Programming Languages Achievement Award---the most significant international career award in programming languages. He received the award for his "foundational contributions to our understanding of type theory and its use in the design, specification, implementation, and verification of modern programming languages".

Award Citation:

Robert (Bob) Harper is widely known for his foundational contributions to our understanding of type theory and its use in the design, specification, implementation, and verification of modern programming languages. Bob demonstrated that sound type systems and operational semantics are not only appropriate vehicles for reasoning about idealized languages, but that this theory can be applied to complex, modern languages. His achievements include analysis of language features ranging from references to continuations to modules, the definition of a variety of new type systems, the idea of using types throughout the compilation process, the analysis of run-time system semantics and cost, a formal definition of Standard ML and its mechanization, the definition of logical framework LF and other logical frameworks based on homotopy type theory.

Some of Bob’s most influential work involved the design, theory and implementation of the TIL (Typed Intermediate Language) compiler system, which pioneered the idea that compilers can propagate type information to lower-level intermediate languages, where it can be used to guide optimizations and to catch compiler bugs. These ideas led directly to the development of proof-carrying code, typed assembly language, and a wide array of type-preserving compilers.

Bob Harper has also had a profound impact though his mentorship, teaching and the influence of his books “Programming in Standard ML” and “Practical Foundations for Programming Languages.”

Adish Singla, head of the MPI-SWS Machine Teaching Research group, has been awarded a 2021 ERC Starting Grant. Over the next five years, his project TOPS will receive funding of 1.5 million euros for research on "Machine-Assisted Teaching for Open-Ended Problem Solving: Foundations and Applications". Read more about the TOPS project below.

ERC grants are the most prestigious and the most competitive European-level awards for ground-breaking scientific investigations. This year, less than 10% of all ERC Starting Grant applicants across all scientific disciplines received the award, with only 23 awardees in Computer Science across all of Europe! You can find more information about ERC Starting Grants awarded this year at https://erc.europa.eu/news/StG-recipients-2021.

The TOPS Project

Computational thinking and problem solving skills are essential for everyone in the 21st century, both for students to excel in STEM+Computing fields and for adults to thrive in the digital economy. Consequently, educators are putting increasing emphasis on pedagogical tasks in open-ended domains such as programming, conceptual puzzles, and virtual reality environments.

When learning to solve such open-ended tasks by themselves, people often struggle. The difficulties are embodied in the very nature of tasks being open-ended: (a) underspecified (multiple solutions of variable quality), (b) conceptual (no well-defined procedure), (c) sequential (series of interdependent steps needed), and (d) exploratory (multiple pathways to reach a solution). These struggling learners can benefit from individualized assistance, for instance, by receiving personalized curriculum across tasks or feedback within a task. Unfortunately, human tutoring resources are scarce, and receiving individualized human-assistance is rather a privilege. Technology empowered by artificial intelligence has the potential to tackle this scarcity challenge by providing scalable and automated machine-assisted teaching. However, the state-of-the-art technology is limited: it is designed for well-defined procedural learning, but not for open-ended conceptual problem solving.

The TOPS project will develop next-generation technology for machine-assisted teaching in open-ended domains. We will design novel algorithms for assisting the learner by bridging reinforcement learning, imitation learning, cognitive science, and symbolic reasoning. Our theoretical foundations will be based on a computational framework that models the learner as a reinforcement learning agent who gains mastery with the assistance of an automated teacher. In addition to providing solid foundations, we will demonstrate the performance of our techniques in a wide range of pedagogical applications.