Technische Universität Wien
Institute of Logic and Computation
Favoritenstraße 9–11, E192-01
|Room:||HB0412 (how to get there)|
- Structural Graph Theory.
Since many important graph problems are hard in general, I am interested in finding the most general graph classes for which problems remain tractable. I worked a lot with the notion of bounded expansion and nowhere denseness, which provide a very robust way to capture sparse graphs. Currently, I am interested in first-order transductions of such graph classes. They seem to provide an elegant way to describe dense graphs that have similar algorithmic properties as their sparse counterparts.
- Logic in Computer Science.
For a fixed logic, the model-checking problem asks whether a given sentence from that logic holds on a given structure. I like working on this problem because it generalizes whole classes of other problems and therefore can lead to new tractability results for all these problems in one go.
- Random Structures and Average Case Complexity.
Network scientists use random graph models to describe complex networks. I am curious about the algorithmic properties of these random graphs.