The search for the limits of search speed - Karl Bringmann receives prestigeous research award

Karl Bringmann, Senior Researcher at the MPI for Informatics, has been awarded an ERC Grant by the European Research Council, the most prestigious European research award. Within the next five years, 1.5 million euros from his ERC Starting Grant will be available to him for research work on fine-grained complexity theory / linear programming.

At the first reading, the term fine-granular complexity theory / linear programming appears to be arbitrarily far away from daily life. The experts at the European Research Council, however, took a different view. In a broader sense, the research topic deals with how quickly a computer algorithm can find the best of all possible solutions to difficult problems.

The computer-aided compilation of shift schedules or timetables is now commonplace. Here, as well as with other optimization tasks, algorithms are used which ensure that usually very good solutions can be found, sometimes even optimal results. A similar situation is searching for words or fragments in texts. The development of faster search algorithms has therefore been given a lot of attention since the beginning of the computer era. The knowledge about the limits of the theoretically possible efficiency of such algorithms avoids unnecessary efforts.

Here begins the field of complexity theory, a subfield of theoretical computer science: What is the minimum resource consumption (computing time, memory space requirement, perhaps parallelizability) required to solve a given problem?  

“What makes complexity theory interesting for me is the possibility of finding certain limits that cannot be overcome. The difficulties of gaining knowledge are very high, but the satisfaction after a result is very high as well,” Karl Bringmann outlines his motivation: “Even if it sometimes takes a very long time for a certain hypothesis to be decided, the chance of opening or closing this one door forever is tempting.”

Thanks to the award, Karl Bringmann can now continue to work on the topic for five years with talented young employees. He is hoping for proven research results, i.e. mathematically undisputed ones, that show that there can be no faster solutions to certain problems, i.e. that further searching for them is doomed to failure beforehand.

Parallel to Karl Bringmann, two other young scientists who recently did research at the Max Planck Institutes in Saarbrücken were awarded the coveted prize: Zeynep Akata (until 2017 postdoc at the MPI for Informatics, currently Univ. of Amsterdam) and Ori Lahav (until 2017 Postdoc at the MPI for Software Systems, currently Univ. of Tel Aviv).