Jan Dreier

According to our database, Jan Dreier authored at least 32 papers between 2014 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Corrigendum to "Twin-width and generalized coloring numbers" [Discrete Math. 345 (3) (2022) 112746].

Jan Dreier, Jakub Gajarský, Yiting Jiang, Patrice Ossona de Mendez, Jean-Florent Raymond

Discret. Math., January, 2024

SAT backdoors: Depth beats size.

Jan Dreier, Sebastian Ordyniak, Stefan Szeider

J. Comput. Syst. Sci., 2024

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes.

Jan Dreier, Nikolas Mählmann, Szymon Torunczyk

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

CSP beyond tractable constraint languages.

Jan Dreier, Sebastian Ordyniak, Stefan Szeider

Constraints An Int. J., September, 2023

Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes.

Jan Dreier

Log. Methods Comput. Sci., 2023

First-Order Model Checking on Monadically Stable Graph Classes.

Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, Szymon Torunczyk

CoRR, 2023

Approximate Evaluation of Quantitative Second Order Queries.

Jan Dreier, Robert Ganian, Thekla Hamm

CoRR, 2023

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, 2023

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, 2023

Pseudorandom Finite Models.

Jan Dreier, Jamie Tucker-Foltz

Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023

Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes.

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond.

Jan Dreier, Daniel Mock, Peter Rossmanith

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Twin-width and generalized coloring numbers.

Jan Dreier, Jakub Gajarský, Yiting Jiang, Patrice Ossona de Mendez, Jean-Florent Raymond

Discret. Math., 2022

Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes.

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk

CoRR, 2022

Treelike Decompositions for Transductions of Sparse Graphs.

Jan Dreier, Jakub Gajarský, Sandra Kiefer, Michal Pilipczuk, Szymon Torunczyk

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth.

Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Combinatorial and Algorithmic Aspects of Monadic Stability.

Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, Alexandre Vigny

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

2021

Approximate Evaluation of First-Order Counting Queries.

Jan Dreier, Peter Rossmanith

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes.

Jan Dreier

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

2020

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

Discret. Appl. Math., 2020

Advice for Online Knapsack With Removable Items.

Hans-Joachim Böckenhauer, Jan Dreier, Fabian Frei, Peter Rossmanith

CoRR, 2020

Hard Problems on Random Graphs.

Jan Dreier, Henri Lotze, Peter Rossmanith

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

First-Order Model-Checking in Random Graphs and Complex Networks.

Jan Dreier, Philipp Kuinke, Peter Rossmanith

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size.

Jan Dreier, Philipp Kuinke, Peter Rossmanith

Proceedings of the Approximation, 2020

2019

Hardness of FO Model-Checking on Random Graphs.

Jan Dreier, Peter Rossmanith

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

The Complexity of Packing Edge-Disjoint Paths.

Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, Hung-Lung Wang

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

Motif Counting in Preferential Attachment Graphs.

Jan Dreier, Peter Rossmanith

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2018

The Fine Structure of Preferential Attachment Graphs I: Somewhere-Denseness.

Jan Dreier, Philipp Kuinke, Peter Rossmanith

CoRR, 2018

Local Structure Theorems for Erdős-Rényi Graphs and Their Algorithmic Applications.

Jan Dreier, Philipp Kuinke, Ba Le Xuan, Peter Rossmanith

Proceedings of the SOFSEM 2018: Theory and Practice of Computer Science - 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29, 2018

2017

Local Structure Theorems for Erdos Renyi Graphs and their Algorithmic Application.

Jan Dreier, Philipp Kuinke, Ba Le Xuan, Peter Rossmanith

CoRR, 2017

2014

Overlapping Communities in Social Networks.

Jan Dreier, Philipp Kuinke, Rafael Przybylski, Felix Reidl, Peter Rossmanith, Somnath Sikdar

CoRR, 2014

Overlapping Communities in Complex Networks.

Jan Dreier

CoRR, 2014