Algorithms, Theory, Logic

This field investigates a range of theoretical and practical aspects of algorithmics. Considering all aspects of the process holistically—from analyzing the efficiency and the quality of the solutions, to developing provably efficient and correct software, to packaging and releasing this software—helps to inform the research as well as benefit the community.

Groups and Researchers in this Field

Principles of Security and Privacy

Gilles Barthe's research interests lie in the areas of programming languages and program verification, software and system security, cryptography, formal methods and logic. His goal is to develop foundations and tools for reasoning about security and privacy properties of algorithms and implementations. His recent work focuses on building relational verification methods for probabilistic programs and on their applications in cryptography and privacy. He is also interested in provably secure countermeasures against side-channel attacks. Read more

Gilles Barthe

MPI-SP, Scientific Director
Personal Website

Fine-Grained Complexity and Algorithms

Karl Bringmann leads the group Fine-Grained Complexity and Algorithms in the Algorithms and Complexity department at the Max Planck Institute for Informatics. He is interested in the inherent time complexity of combinatorial problems. Specifically, which problems can be solved in near-linear time, which require quadratic time, etc.? Since NP-hardness is too coarse to answer such questions, the modern approach is to prove conditional lower bounds via fine-grained reductions from certain hardness assumptions; this approach is called fine-grained complexity theory. Karl’s group develops this theory and uses a combination of fine-grained lower bounds and algorithm design to determine the optimal time complexity of various problems from computational geometry, stringology, graph theory, and optimization. Read more

Karl Bringmann

MPI-INF, Senior Researcher
Personal Website

Foundations of Programming

Derek Dreyer leads the Foundations of Programming group at the Max Planck Institute for Software Systems. The group focuses on the design, semantics, verification, and implementation of modern programming languages and systems. Topics of study have included advanced type systems for modular programming and verification; Kripke models and separation logics for reasoning about higher-order, imperative, and concurrent programs; and compositional compiler certification. Derek is interested in developing a “realistic” theory of modularity—figuring out how we can build and reason modularly about programs that use features like fine-grained concurrency, higher-order state, recursive linking, dependent types, or self-modifying assembly code, meaning traditional semantic and verification techniques cannot account for them. Read more

Derek Dreyer

MPI-SWS, Faculty
Personal Website

Foundations of Computer Security

Deepak Garg’s interests include computer security and privacy, formal logic, and programming languages. He is head of the Foundations of Computer Security group, associated with both the Security & Privacy and the Programming Languages & Verification research areas at the Max Planck Institute for Software Systems. The group’s current projects investigate tracking and controlling flows of sensitive information through Web browsers, using type systems to statically estimate the asymptotic complexity of incremental runs of programs, creating mechanisms to enforce data protection policies across multiple system infrastructure layers, extending separation logics to reason about security protocols, and developing foundations and algorithms for temporal logic-based privacy audits of legal compliance, among others. Read more

Deepak Garg

MPI-SWS, Faculty
Personal Website

Probabilistic Numerics

Philipp Hennig holds the Chair for the Methods of Machine Learning, and is an adjunct scientist at the Max Planck Institute for Intelligent Systems. He studied Physics in Heidelberg, Germany and at Imperial College, London, before moving to the University of Cambridge, UK, where he attained a PhD in the group of Sir David JC MacKay with research on machine learning. Since this time, he is interested in connections between computation and inference. With international collaborators, he helped establish the field of probabilistic numerics. His research was supported, among others, by the Emmy Noether Programme of the German Research Union (DFG), an independent Research Group of the Max Planck Society, and a Starting Grant of the European Commission. Read more

Philipp Hennig

MPI-IS, Adjunct Faculty
Personal Website

Formally Verified Security

Cătălin Hrițcu is a tenured faculty member at the Max Planck Institute for Security and Privacy (MPI-SP). He is particularly interested in security foundations (secure compilation, compartmentalization, memory safety, security protocols, information flow), programming languages (program verification, proof assistants, dependent types, formal semantics, mechanized metatheory, property-based testing), and the design and verification of secure systems (reference monitors, secure compilation chains, tagged architectures). He was awarded an ERC Starting Grant on formally secure compilation and is also actively involved in the design of the F* verification system. Read more

Cătălin Hrițcu

MPI-SP, Faculty
Personal Website

Discrete Optimization

Discrete optimization problems are ubiquitous. Whenever there is a choice between several possibilities, there is an inherent optimization problem. Our core competence in this area is to recognize such optimization problems, to establish mathematical models, to tackle them by state-of-the-art methods, and to invent new techniques to obtain satisfactory results. Our research is application-driven. This also includes inter-disciplinary research with collaborators from engineering, physics, chemistry, biology, economics, etc. Read more

Andreas Karrenbauer

MPI-INF, Senior Researcher
Personal Website

Rigorous Software Engineering

Rupak Majumdar is a Scientific Director at the Max Planck Institute for Software Systems, where he leads the Rigorous Software Engineering group. His main research interests include verification and control of reactive, real-time, hybrid, and probabilistic systems, software verification and programming languages, logic, and automata theory. His group investigates both foundational principles and practical tools for the design and analysis of computer systems. Some recent research directions have included methodologies and tools for the automated co-design of embedded controllers and their implementations, foundations of robustness for hybrid systems, scalable tools for coverability analysis of Petri nets, algorithms for the analysis of infinite-state systems, and verification of asynchronous programs. Read more