Marc Roth

According to our database, Marc Roth authored at least 29 papers between 2017 and 2024.

Collaborative distances:

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

2024

Parameterised and Fine-Grained Subgraph Counting, Modulo 2.

Leslie Ann Goldberg, Marc Roth

Algorithmica, April, 2024

Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process.

Leslie Ann Goldberg, Marc Roth, Tassilo Constantin Schwarz

Theor. Comput. Sci., 2024

Counting Small Induced Subgraphs with Hereditary Properties.

Jacob Focke, Marc Roth

SIAM J. Comput., 2024

Counting Subgraphs in Somewhere Dense Graphs.

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

SIAM J. Comput., 2024

Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity.

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný

Proc. ACM Manag. Data, 2024

The Weisfeiler-Leman Dimension of Conjunctive Queries.

Andreas Göbel, Leslie Ann Goldberg, Marc Roth

Proc. ACM Manag. Data, 2024

Parameterised Holant Problems.

Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, Johannes Schmitt

CoRR, 2024

2023

Parameterized Counting and Cayley Graph Expanders.

Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina, Philip Wellnitz

SIAM J. Discret. Math., June, 2023

The Weisfeiler-Leman Dimension of Existential Conjunctive Queries.

Andreas Göbel, Leslie Ann Goldberg, Marc Roth

CoRR, 2023

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

Marco Bressan, Matthias Lanzinger, Marc Roth

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

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

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

Algorithmica, 2022

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

2021

Counting Homomorphisms to K₄-Minor-Free Graphs, Modulo 2.

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný

SIAM J. Discret. Math., 2021

Counting homomorphisms, subgraphs, and induced subgraphs in degenerate graphs: new hardness results and complete complexity classifications.

Marco Bressan, Marc Roth

CoRR, 2021

Parameterized Counting of Partially Injective Homomorphisms.

Marc Roth

Algorithmica, 2021

Counting Homomorphisms to <i>K</i>₄-minor-free Graphs, modulo 2.

Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný

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

Parameterized (Modular) Counting and Cayley Graph Expanders.

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

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

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

Marc Roth, Johannes Schmitt, Philip Wellnitz

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

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

Marco Bressan, Marc Roth

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

The weak call-by-value λ-calculus is reasonable for both time and space.

Yannick Forster, Fabian Kunze, Marc Roth

Proc. ACM Program. Lang., 2020

Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness.

Marc Roth, Johannes Schmitt

Algorithmica, 2020

Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory.

Marc Roth, Philip Wellnitz

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

Counting Small Induced Subgraphs Satisfying Monotone Properties.

Marc Roth, Johannes Schmitt, Philip Wellnitz

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Counting problems on quantum graphs.

Marc Roth

PhD thesis, 2019

Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes.

Radu Curticapean, Holger Dell, Marc Roth

Theory Comput. Syst., 2019

Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP.

Cornelius Brand, Holger Dell, Marc Roth

Algorithmica, 2019

Counting Answers to Existential Questions.

Holger Dell, Marc Roth, Philip Wellnitz

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2017

Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices.

Marc Roth

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Parameterized Counting of Trees, Forests and Matroid Bases.

Cornelius Brand, Marc Roth

Proceedings of the Computer Science - Theory and Applications, 2017