Supervisor

Suitable for

Abstract

Graphs are a common model for relations between entities. A fundamental computational problem when dealing with graphs is that of isomorphism, the structural equivalence of two graphs. To handle the complexity algorithmically, canonical representations of the input graphs are often beneficial. In the search for such representations, one tries to make use of the properties of the considered graph class. Approaches to comparing graphs involve tools from combinatorics, finite-model theory, algorithms, and machine learning.

 

Graphs and relational structures are also used as models of computation, for example, in the shape of transducers that transform strings into a binary or a more sophisticated output. Petri nets and some population protocols are abstractions for distributed computing with graph-like elements. In the context of graph-based computation models, mathematical logic has turned out to be fruitful to capture expressivity and to tackle verification questions.

 

Sandra Kiefer supervises projects with connections to theoretical computer science, more precisely, topics in structural graph theory and graph algorithms, mathematical logic, automata theory, and graph neural networks. The projects can be purely theoretical or have practical components. Interested students should have knowledge in some of the aforementioned fields and a high interest in formalising concepts, building theories, and proving theorems.