Publications: Jan Niclas Dreier

Efficient reversal of transductions of sparse graph classes Jan Dreier, Jakub Gajarský, Michał Pilipczuk.
📄 Details

Approximate Evaluation of Quantitative Second Order Queries Dreier, Jan, Ganian, Robert, Hamm, Thekla. 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
📄 Details
Merge-Width and First-Order Model Checking Dreier, Jan, Toruńczyk, Szymon. Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC)
📄 Details

First-Order Model Checking on Monadically Stable Graph Classes Dreier, Jan, Eleftheriadis, Ioannis, Mählmann, Nikolas, McCarty, Rose, Pilipczuk, Michał, Toruńczyk, Szymon. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
📄 Details
Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes Dreier, Jan, Mählmann, Nikolas, Toru\ŉczyk, Szymon. Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC)
📄 Details
SAT backdoors: Depth beats size Jan Dreier, Sebastian Ordyniak, Stefan Szeider. Journal of Computer and System Sciences
📄 Details

Pseudorandom Finite Models Jan Dreier, Jamie Tucker-Foltz. LICS
📄 Details
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)
📄 Details
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
📄 Details
Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond Dreier, Jan, Mock, Daniel, Rossmanith, Peter. 31st Annual European Symposium on Algorithms (ESA 2023)
📄 Details
CSP beyond tractable constraint languages Jan Dreier, Sebastian Ordyniak, Stefan Szeider. Constraints
📄 Details
First-Order Model Checking on Structurally Sparse Graph Classes Dreier, Jan, Mählmann, Nikolas, Siebertz, Sebastian. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023
📄 Details

Treelike Decompositions for Transductions of Sparse Graphs Dreier, Jan, Gajarský, Jakub, Kiefer, Sandra, Pilipczuk, Michał, Toruńczyk, Szymon. Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
📄 Details
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth Bonnet, Édouard, Dreier, Jan, Gajarský, Jakub, Kreutzer, Stephan, Mählmann, Nikolas, Simon, Pierre, Toruńczyk, Szymon. Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022)
📄 Details
Twin-width and generalized coloring numbers Jan Dreier, Jakub Gajarský, Yiting Jiang, Patrice Ossona de Mendez, Jean-Florent Raymond. Discrete Mathematics
📄 Details
Combinatorial and Algorithmic Aspects of Monadic Stability Dreier, Jan, Mählmann, Nikolas, Mouawad, Amer E., Siebertz, Sebastian, Vigny, Alexandre. 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
📄 Details
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
📄 Details
SAT Backdoors: Depth Beats Size Jan Dreier, Sebastian Ordyniak, Stefan Szeider. 30th Annual European Symposium on Algorithms (ESA 2022)
📄 Details

Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes Dreier, Jan. 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
📄 Details
Approximate Evaluation of First-Order Counting Queries Dreier, Jan, Rossmanith, Peter. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
📄 Details

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.
📄 Details
First-Order Model-Checking in Random Graphs and Complex Networks Jan Dreier, Philipp Kuinke, Peter Rossmanith. 28th Annual European Symposium on Algorithms (ESA 2020)
📄 Details
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)
📄 Details
Hard Problems on Random Graphs Jan Dreier, Henri Lotze, Peter Rossmanith. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
📄 Details

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)
📄 Details
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)
📄 Details
Hardness of FO Model-Checking on Random Graphs Jan Dreier, Peter Rossmanith. 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
📄 Details

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)
📄 Details