Publications
Andreas Göbel, Leslie Ann Goldberg and Marc Roth
The Weisfeiler-Leman Dimension of Conjunctive Queries
PODS 2024 (to appear) / arXiv 2023
Jacob Focke, Leslie Ann Goldberg, Marc Roth and Stanislav Živný
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
PODS 2024 (to appear) / arXiv 2023
Leslie Ann Goldberg and Marc Roth
Parameterised and Fine-Grained Subgraph Counting, modulo 2
Marco Bressan, Matthias Lanzinger and Marc Roth
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, and Marc Roth
Counting Subgraphs in Somewhere Dense Graphs
SIAM Journal on Computing (to appear) / ITCS 2023 / arXiv 2022
Jacob Focke, Leslie Ann Goldberg, Marc Roth and Stanislav Živný
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
Jacob Focke and Marc Roth
Counting Small Induced Subgraphs with Hereditary Properties
Marco Bressan and Marc Roth
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
FOCS 2021 (took place in Feb. 2022) / arXiv 2021
Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina and Philip Wellnitz
Parameterized Counting and Cayley Graph Expanders
SIAM Journal on Discrete Mathematics 2023
Part 1: ICALP 2021 / arXiv 2020 (with Johannes Schmitt and Philip Wellnitz)
Part 2: MFCS 2021 / arXiv 2021 (with Norbert Peyerimhoff, Johannes Schmitt, Jakob Stix and Alina Vdovina)
Jacob Focke, Leslie Ann Goldberg, Marc Roth and Stanislav Živný
Counting Homomorphisms to K4-minor-free Graphs, modulo 2
SIAM Journal on Discrete Mathematics 2021 / SODA 2021 / arXiv 2020
Marc Roth, Johannes Schmitt and Philip Wellnitz
Counting Small Induced Subgraphs Satisfying Monotone Properties
Yannick Forster, Fabian Kunze and Marc Roth
The Weak Call-By-Value λ-Calculus is Reasonable for Both Time and Space
Marc Roth and Philip Wellnitz
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
Julian Dörfler, Marc Roth, Johannes Schmitt and Philip Wellnitz
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
Holger Dell, Marc Roth and Philip Wellnitz
Counting Answers to Existential Questions
Marc Roth and Johannes Schmitt
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness
IPEC 2018 Best Paper Award and IPEC 2018 Excellent Student Paper Award
Marc Roth
Parameterized Counting of Partially Injective Homomorphisms
ESA 2017 Best Student Paper Award
Algorithmica 2021 / ESA 2017 (past version) / arXiv 2017 (past version)
Cornelius Brand and Marc Roth
Parameterized Counting of Trees, Forests and Matroid Bases
Radu Curticapean, Holger Dell and Marc Roth
Counting Edge-Injective Homomorphisms and Matchings in Restricted Graph Classes
Cornelius Brand, Holger Dell and Marc Roth
Fine-Grained Dichotomies for the Tutte plane and Boolean #CSP
IPEC 2016 Best Paper Award
PhD Thesis
thesis.pdfMarc Roth
Counting Problems on Quantum Graphs: Parameterized and Exact Complexity Classifications
Saarland University 2019
Manuscripts
Leslie Ann Goldberg, Marc Roth and Tassilo Constantin Schwarz