Jan Dreier
Address:
Jan Dreier
Technische Universität Wien
Institute of Logic and Computation
Favoritenstraße 9–11, E192-01
1040 Wien
Austria
| Room: | HB0412 (how to get there) |
| Phone: | +43(1)58801–192146 |
| Email: | dreier@ac.tuwien.ac.at |
| Web: | http://www.ac.tuwien.ac.at/people/dreier/ |
I am a Postdoc at the Algorithms and Complexity Group at Vienna University of Technology. Before, I received my PhD at the Theory Group at RWTH Aachen University.
Research Interests
- 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.
Recent Presentations
- Slides and video of my talk about approximate evaluation of first-order counting queries at SODA 2021.
- Slides and video of my talk about first-order model-checking in random graphs and complex networks at ESA 2020.
- Slides and video of my talk about shallow clique minors in preferential attachment graphs at RANDOM 2020.
PhD Thesis
My PhD thesis with the title "Two New Perspectives on Algorithmic Meta-Theorems".
