Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

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, as well as monadically stable and monadically NIP graph classes.
  • Algorithmic Meta-Theorems. The model-checking problem asks whether a given logical sentence holds on a given structure. I like working on this problem because it generalizes many other problems and therefore can lead to very general tractability results.

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.

Publications

18 results
2023
[18]A logic-based algorithmic meta-theorem for mim-width
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), 2023, SIAM.
[bibtex] [pdf]
2022
[17]Twin-width and generalized coloring numbers
Jan Dreier, Jakub Gajarský, Yiting Jiang, Patrice Ossona de Mendez, Jean-Florent Raymond
Discrete Mathematics, volume 345, number 3, pages 112746, 2022.
[bibtex] [pdf] [doi]
[16]SAT Backdoors: Depth Beats Size
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
(Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman, eds.), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:18, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[15]CSP Beyond Tractable Constraint Languages
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
28th International Conference on Principles and Practice of Constraint Programming, CP 2022, July 31 to August 8, 2022, Haifa, Israel (Christine Solnon, ed.), volume 235 of LIPIcs, pages 20:1–20:17, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[14]Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022), 2022, Association for Computing Machinery.
[bibtex] [pdf]
[13]Treelike Decompositions for Transductions of Sparse Graphs
Jan Dreier, Jakub Gajarský, Sandra Kiefer, Michał Pilipczuk, Szymon Toruńczyk
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022), 2022, Association for Computing Machinery.
[bibtex] [pdf]
[12]Combinatorial and Algorithmic Aspects of Monadic Stability
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, Alexandre Vigny
2022, arXiv.
[bibtex] [pdf] [doi]
[11]Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Toruńczyk
2022, arXiv.
[bibtex] [pdf] [doi]
2021
[10]Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes
Jan Dreier
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-13, 2021.
Note: distinguished paper
[bibtex] [doi]
[9]Approximate Evaluation of First-Order Counting Queries
Jan Dreier, Peter Rossmanith
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), 2021, SIAM.
[bibtex] [pdf] [doi]
2020
[8]Complexity of independency and cliquy trees
Katrin Casel, Jan Dreier, Henning Fernau, Moritz Gobbert, Philipp Kuinke, Fernando Sánchez Villaamil, Markus L. Schmid, Erik Jan van Leeuwen
Discr. Appl. Math., volume 272, pages 2–15, 2020.
[bibtex] [pdf] [doi]
[7]Hard Problems on Random Graphs
Jan Dreier, Henri Lotze, Peter Rossmanith
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:14, 2020, Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[6]Maximum Shallow Clique Minors in Preferential Attachment Graphs have Polylogarithmic Size
Jan Dreier, Philipp Kuinke, Peter Rossmanith
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), volume 176 of LIPIcs, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[5]First-Order Model-Checking in Random Graphs and Complex Networks
Jan Dreier, Philipp Kuinke, Peter Rossmanith
28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of LIPIcs, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf]
2019
[4]Hardness of FO Model-Checking on Random Graphs
Jan Dreier, Peter Rossmanith
14th International Symposium on Parameterized and Exact Computation (IPEC 2019), volume 148 of LIPIcs, pages 11:1–11:15, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [doi]
[3]Motif Counting in Preferential Attachment Graphs
Jan Dreier, Peter Rossmanith
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), volume 150 of LIPIcs, pages 13:1–13:14, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[bibtex] [pdf] [doi]
[2]The Complexity of Packing Edge-Disjoint Paths
Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, Hung-Lung Wang
14th International Symposium on Parameterized and Exact Computation (IPEC 2019), volume 148 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:16, 2019, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[bibtex] [pdf] [doi]
2018
[1]Local Structure Theorems for Erdos-Rényi Graphs and Their Algorithmic Applications
Jan Dreier, Philipp Kuinke, Ba Le Xuan, Peter Rossmanith
44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018), volume 10706 of Lecture Notes in Computer Science, pages 125–136, 2018, Springer Verlag.
[bibtex] [pdf] [doi]
  • Cornelius Brand
  • Doris Brazda
  • Jiehua Chen
  • Alexis de Colnet
  • Alexander Dobler
  • Jan Dreier
  • Herbert Fleischner
  • Nikolaus Frohner
  • Robert Ganian
  • Christian Hatschka
  • Marc Huber
  • Enrico Iurlano
  • Thomas Jatschka
  • Liana Khazaliya
  • Markus Kirchweger
  • Viktoria Korchemna
  • Martin Kronegger
  • Andreas Müller
  • Martin Nöllenburg
  • Daniel Obszelka
  • Tomáš Peitl
  • Vaidyanathan P. R.
  • Günther Raidl
  • Franz Xaver Reichl
  • Mathis Rocton
  • Andre Schidler
  • Sofia Simola
  • Friedrich Slivovsky
  • Manuel Sorge
  • Stefan Szeider
  • Soeren Terziadis
  • Johannes Varga
  • Anaïs Villedieu
  • Markus Wallinger
  • Jules Wulms
  • Hai Xia
  • Tianwei Zhang
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.