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 (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.

Publications

9 results
2021
[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.
Note: To be published
[bibtex] [pdf]
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]
  • Jiehua Chen
  • Leroy Chew
  • Doris Dicklberger
  • Marko Djukanovic
  • Jan Dreier
  • Herbert Fleischner
  • Nikolaus Frohner
  • Robert Ganian
  • Thekla Hamm
  • Matthias Horn
  • Marc Huber
  • Thomas Jatschka
  • Martin Kronegger
  • Guangping Li
  • Andreas Müller
  • Soeren Nickel
  • Martin Nöllenburg
  • Daniel Obszelka
  • Vaidyanathan P. R.
  • Günther Raidl
  • Franz Xaver Reichl
  • Sanjukta Roy
  • Andre Schidler
  • Friedrich Slivovsky
  • Manuel Sorge
  • Stefan Szeider
  • Anaïs Villedieu
  • Markus Wallinger
  • Jules Wulms
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.