Publications

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

Counting Subgraphs in Somewhere Dense Graphs

ITCS 2023 (to appear) / arXiv 2022

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

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations

PODS 2022 / arXiv 2021

Jacob Focke and Marc Roth

Counting Small Induced Subgraphs with Hereditary Properties

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 (to appear)
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

Marco Bressan, Matthias Lanzinger and Marc Roth

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

arXiv 2022