Our research is primarily dedicated to computational problems on abstract networks (so-called graphs) that represent relationships between objects, such as those found in social networks or road networks. For such problems, we develop algorithms using mathematical methods from algebra, for example by translating data into polynomials and further processing this data through algebraic manipulations of the associated polynomials. Studying the complexity of such polynomials in a self-contained manner leads to the area of algebraic complexity theory.
Our work is partially financed by the ERC Starting Grant COUNTHOM. This project investigates exciting connections between various combinatorial problems: It turns out that fundamental computational problems that have previously been studied independently, mostly related to testing and counting small patterns in networks, can be viewed as one and the same problem from the right perspective! This generalizing perspective is made possible by so-called homomorphisms, structure-preserving mappings. In the COUNTHOM project, we will use homomorphisms to gain a deeper understanding and thereby develop optimal algorithms for such computational problems.
