Publications

Leslie Ann Goldberg and Marc Roth

Parameterised and Fine-Grained Subgraph Counting, modulo 2

Algorithmica 2023 / ICALP 2023 / arXiv 2023

Marco Bressan, Matthias Lanzinger and Marc Roth

The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree

STOC 2023 / arXiv 2022

Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, and Marc Roth

Counting Subgraphs in Somewhere Dense Graphs

ITCS 2023 / arXiv 2022

Jacob Focke, Leslie Ann Goldberg, Marc Roth and Stanislav Živný 

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations 

PODS 2022arXiv 2021

Jacob Focke and Marc Roth 

Counting Small Induced Subgraphs with Hereditary Properties

SIAM Journal on Computing (to appear) / STOC 2022 / arXiv 2021

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

SIAM Journal on Computing 2022 / FOCS 2020 / arXiv 2020

Yannick Forster, Fabian Kunze and Marc Roth

The Weak Call-By-Value λ-Calculus is Reasonable for Both Time and Space

POPL 2020 / arXiv 2019

Marc Roth and Philip Wellnitz

Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory

SODA 2020 / arXiv 2019

Julian Dörfler, Marc Roth, Johannes Schmitt and Philip Wellnitz

Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness

Algorithmica 2021 / MFCS 2019 / arXiv 2019

Holger Dell, Marc Roth and Philip Wellnitz

Counting Answers to Existential Questions

ICALP 2019 / arXiv 2019

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

Algorithmica 2020 / IPEC 2018 / arXiv 2018

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

CSR 2017 / arXiv 2017

Radu Curticapean, Holger Dell and Marc Roth

Counting Edge-Injective Homomorphisms and Matchings in Restricted Graph Classes

Theory of Computing Systems 2019 / STACS 2017 / arXiv 2017

Cornelius Brand, Holger Dell and Marc Roth

Fine-Grained Dichotomies for the Tutte plane and Boolean #CSP

IPEC 2016 Best Paper Award

Algorithmica 2019 / IPEC 2016 / arXiv 2016

PhD Thesis

thesis.pdf

Marc Roth

Counting Problems on Quantum Graphs: Parameterized and Exact Complexity Classifications

Saarland University 2019 

Manuscripts

Andreas Göbel, Leslie Ann Goldberg and Marc Roth

The Weisfeiler-Leman Dimension of Existential Conjunctive Queries

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

arXiv 2023

Leslie Ann Goldberg, Marc Roth and Tassilo Constantin Schwarz

Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process

arXiv 2023