Publications

Marco Bressan and Marc Roth

Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies

FOCS 2021 (to appear) / arXiv 2021

Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix and Alina Vdovina

Parameterized (Modular) Counting and Cayley Graph Expanders

MFCS 2021 / arXiv 2021

Marc Roth, Johannes Schmitt and Philip Wellnitz

Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders

ICALP 2021 / arXiv 2020

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

Counting Homomorphisms to K4-minor-free Graphs, modulo 2

SIAM Journal on Discrete Mathematics (to appear) / SODA 2021 / arXiv 2020

Marc Roth, Johannes Schmitt and Philip Wellnitz

Counting Small Induced Subgraphs Satisfying Monotone Properties

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

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

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

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations

arXiv 2021