Publications: Jan Niclas Dreier

2026

[1]	Efficient reversal of transductions of sparse graph classes Jan Dreier, Jakub Gajarský, Michał Pilipczuk 2026. [bibtex] [pdf]

2025

[1]	Approximate Evaluation of Quantitative Second Order Queries Jan Dreier, Robert Ganian, Thekla Hamm 40th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2025, Singapore, June 23-26, 2025, pages 664–677, 2025, IEEE. [bibtex] [pdf] [doi]
[2]	Merge-Width and First-Order Model Checking Jan Dreier, Szymon Toruńczyk Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 1944–1955, 2025, Association for Computing Machinery. [bibtex] [pdf] [doi]

2024

[1]	SAT backdoors: Depth beats size Jan Dreier, Sebastian Ordyniak, Stefan Szeider Journal of Computer and System Sciences, volume 142, pages 103520, 2024. [bibtex] [doi]
[2]	First-Order Model Checking on Monadically Stable Graph Classes Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, Szymon Toruńczyk 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 21-30, 2024. [bibtex] [pdf] [doi]
[3]	Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1550–1560, 2024. [bibtex] [pdf]

2023

[1]	CSP beyond tractable constraint languages Jan Dreier, Sebastian Ordyniak, Stefan Szeider Constraints, volume 28, number 3, pages 450–471, 2023. [bibtex] [pdf] [doi]
[2]	A logic-based algorithmic meta-theorem for mim-width Benjamin Bergougnoux, Jan Dreier, Lars Jaffke Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3282-3304, 2023. [bibtex] [pdf] [doi]
[3]	Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond Jan Dreier, Daniel Mock, Peter Rossmanith 31st Annual European Symposium on Algorithms (ESA 2023) (Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman, eds.), volume 274 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1–43:17, 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [bibtex] [pdf] [doi]
[4]	First-Order Model Checking on Structurally Sparse Graph Classes Jan Dreier, Nikolas Mählmann, Sebastian Siebertz Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 567-580, 2023, Association for Computing Machinery. [bibtex] [pdf] [doi]
[5]	Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany (Kousha Etessami, Uriel Feige, Gabriele Puppis, eds.), volume 261 of LIPIcs, pages 125:1–125:18, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. [bibtex] [pdf] [doi]
[6]	Pseudorandom Finite Models Jan Dreier, Jamie Tucker-Foltz LICS, pages 1–13, 2023. [bibtex] [pdf] [doi]

2022

[1]	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]
[2]	Combinatorial and Algorithmic Aspects of Monadic Stability Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, Alexandre Vigny 33rd International Symposium on Algorithms and Computation (ISAAC 2022) (Sang Won Bae, Heejin Park, eds.), volume 248 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:17, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [bibtex] [pdf] [doi]
[3]	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]
[4]	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]
[5]	SAT Backdoors: Depth Beats Size Jan Dreier, Sebastian Ordyniak, Stefan Szeider 30th Annual European Symposium on Algorithms (ESA 2022) (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]
[6]	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]

2021

[1]	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]
[2]	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]

2020

[1]	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]
[2]	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]
[3]	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]
[4]	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]

2019

[1]	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]
[2]	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]
[3]	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.
[bibtex] [pdf] [doi]