ERC Advanced Grant for Martin Grohe

For his project "Symmetry and Similarity", Computer Science Professor Martin Grohe receives an Advanced Grant of the European Research Council, regarded as one of the most prestiguous European research grants.

Graphs are versatile models for representing complex data ranging from chemical molecules to social interactions. Dealing with graphical data and enabling modern data analysis techniques, a fundamental task is to compare graphs and to measure their similarity in a semantically meaningful and algorithmically efficient way. Despite its importance, graph similarity has mostly been studied in specific application areas, often in an ad-hoc manner and re-inventing the same techniques. There exists no general theory of graph similarity. This is not only a major, fundamental gap, but also prevents an efficient use of similarity for a wide range of problems. The goal of this ERC project is to develop such a theory, and to demonstrate its use for problems of practical relevance.

A landmark problem in this context is the graph isomorphism problem, which has been one of the best known open problems in computer science for more than 50 years. It ask for an efficient algorithm deciding
whether two graphs are structurally identical. Within our theory of similarity, we will approach this problem from a new angle.

ERC Advanced Grant funding is aimed at leading researchers who already play a formative role in their field. With an endowment of 2.5 million euros over five years, the Advanced Grant is thus one of the ERC's most prestigious research grants.