Chair of Algorithms and Complexity Theory

Welcome to the website of the?Algorithms and Complexity Theory?group at the University of Regensburg! This newly founded group at the Faculty of Informatics and Data Science at the University of Regensburg investigates the inherent complexity of fundamental computational problems. Our work focuses particularly on counting problems and related questions in algebraic complexity theory. We also use methods from parameterized complexity theory.

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.

The group currently consists of Prof. Dr. Radu Curticapean and Dr. Cornelius Brand, supported by secretary Annett Reisinger. More employees will follow.

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.