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 |
| 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.
Lectures
In 2021, I held a course about algorithmic meta-theorems. If you are interested for example in a simple proof of Courcelle's theorem, you can find slides and recordings of the course here. Besides introducing the basic notions of sparsity, we also go through the proof that first-order properties can be decided in linear time on bounded expansion graph classes.
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.
Presentations
- Slides of my talk about Lacon- and Shrub-decompositions at the 2021 Dagstuhl seminar on Sparsity.
- Slides and video of my talk about Lacon- and Shrub-decompositions at LICS 2021.
- Slides of my talk about Lacon- and Shrub-decompositions at the Automata Theory Seminar in Warsaw.
- Slides of my talk about complex networks and sparsity at the weekly seminar at IUUK.
- Slides of my talk about sparse and dense graphs at the weekly seminar at IUUK.
- 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.
- My talk about algorithmic meta-theorems for exact and approximate counting in sparse graph classes at the algorithms seminar in Bergen.
- My talk about motif counting in preferential attachment graphs at FSTTCS 2019.
- My talk about hardness of first-order model-checking on random graphs at IPEC 2019.
- My talk about concentration bounds for the degrees of vertices in preferential attachment graphs at Random Structures and Algorithms 2019.
- My talk about efficient model-checking for first-order logic on preferential attachment graphs at TACO Day 2018.
PhD Thesis
My PhD thesis with the title "Two New Perspectives on Algorithmic Meta-Theorems". The slides from my defense are here.
