Certifying Computations: Algorithmics meets Software Engineering
Max-Planck-Institute for Informatics –
I am mostly interested in algorithms for difficult combinatorial and geometric problems:
What is the fastest tour from A to B? How to optimally assign jobs to machines? How can a robot move from one location to another one? Algorithms solving such problems are complex and their implementation is error-prone.
How can we make sure that our implementations of such algorithms are reliable? Certifying algorithms are a viable approach towards the goal. The top part of the figure above illustrates the I/O behavior of a conventional program for computing a function f . The user feeds an input x to the program and the program returns an output y. Why should the user believe that y is equal to f (x)? A certifying algorithm for f computes y and a witness (proof) w; w proves that the algorithm has not erred for this particular input. The certifying algorithms is accompanied by a checker program C. It accepts the triple (x;y;w) if and only if w is a valid witness for the equality y = f (x). Certifying algorithms are the design principle for LEDA, the library of efficient data types and algorithms ([MN99]).
In the first part of the talk, we introduce the concept of certifying algorithms and discuss its significance.. In the second part of the talk, we survey certifying algorithms ([MMNS11]). In the third part of the talk, we discuss the formal verification of certifying computations ([ABMR14, NRM14]).
Kurt Mehlhorn heads the department “Algorithms and Complexity” at the Max Planck Institute for Informatics in Saarbrücken. He is author or co-author of approx. 300 research papers and has published six books. 80 of his former students now hold professorships. Mehlhorn has been awarded a number of prestigious research prizes. These include the Leibniz Prize of the German Research Foundation in 1986 and the Konrad Zuse Medal in 1995. He was Vice President of the Max Planck Society from 2002 to 2008. In 2014, he celebrated his 30th anniversary as a university teacher. He is a member of the Leopoldina, the National Academy of Sciences, of acatech, the National Academy of Science and Engineering, the Academia Europaea, and the Indian National Academy of Engineering. Last year, members of the US National Academy of Science appointed him as a “Foreign Associate” in their ranks. He is the second European computer scientist to be honored this way. In 1995 he co-founded the Algorithmic Solution Software GmbH.
Rodrigo Seromenho Miragaia Rodrigues