Marc Roth

Publication Activity (10 Years)

Years Active: 2016-2024
Publications (10 Years): 54

Top Topics

Exact And Approximate

Conjunctive Queries

Top Venues

Publications

Andreas Göbel, Leslie Ann Goldberg, Marc Roth
The Weisfeiler-Leman Dimension of Conjunctive Queries. Proc. ACM Manag. Data 2 (2) (2024)
Leslie Ann Goldberg, Marc Roth, Tassilo Constantin Schwarz
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process. Theor. Comput. Sci. 1016 (2024)
Leslie Ann Goldberg, Marc Roth
Parameterised and Fine-Grained Subgraph Counting, Modulo 2. Algorithmica 86 (4) (2024)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity. Proc. ACM Manag. Data 2 (2) (2024)
Jacob Focke, Marc Roth
Counting Small Induced Subgraphs with Hereditary Properties. SIAM J. Comput. 53 (2) (2024)
Leslie Ann Goldberg, Marc Roth, Tassilo Constantin Schwarz
Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process. CoRR (2023)
Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina, Philip Wellnitz
Parameterized Counting and Cayley Graph Expanders. SIAM J. Discret. Math. 37 (2) (2023)
Marco Bressan, Matthias Lanzinger, Marc Roth
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree. STOC (2023)
Leslie Ann Goldberg, Marc Roth
Parameterised and Fine-grained Subgraph Counting, modulo 2. CoRR (2023)
Andreas Göbel, Leslie Ann Goldberg, Marc Roth
The Weisfeiler-Leman Dimension of Existential Conjunctive Queries. CoRR (2023)
Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, Marc Roth
Counting Subgraphs in Somewhere Dense Graphs. ITCS (2023)
Leslie Ann Goldberg, Marc Roth
Parameterised and Fine-Grained Subgraph Counting, Modulo 2. ICALP (2023)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity. CoRR (2023)
Marco Bressan, Matthias Lanzinger, Marc Roth
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree. CoRR (2022)
Jacob Focke, Marc Roth
Counting small induced subgraphs with hereditary properties. STOC (2022)
Marco Bressan, Marc Roth
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies. FOCS (2022)
Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, Marc Roth
Counting Subgraphs in Somewhere Dense Graphs. CoRR (2022)
Julian Dörfler, Marc Roth, Johannes Schmitt, Philip Wellnitz
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness. Algorithmica 84 (2) (2022)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. PODS (2022)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. CoRR (2021)
Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina
Parameterized (Modular) Counting and Cayley Graph Expanders. MFCS (2021)
Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina
Parameterized (Modular) Counting and Cayley Graph Expanders. CoRR (2021)
Marc Roth, Johannes Schmitt, Philip Wellnitz
Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders. ICALP (2021)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
-minor-free Graphs, modulo 2. SODA (2021)
Marc Roth
Parameterized Counting of Partially Injective Homomorphisms. Algorithmica 83 (6) (2021)
Marco Bressan, Marc Roth
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies. FOCS (2021)
Marco Bressan, Marc Roth
Counting homomorphisms, subgraphs, and induced subgraphs in degenerate graphs: new hardness results and complete complexity classifications. CoRR (2021)
Jacob Focke, Marc Roth
Counting Small Induced Subgraphs with Hereditary Properties. CoRR (2021)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
-Minor-Free Graphs, Modulo 2. SIAM J. Discret. Math. 35 (4) (2021)
Marc Roth, Johannes Schmitt, Philip Wellnitz
Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders. CoRR (2020)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivný
-minor-free Graphs, modulo 2. CoRR (2020)
Marc Roth, Johannes Schmitt, Philip Wellnitz
Counting Small Induced Subgraphs Satisfying Monotone Properties. CoRR (2020)
Yannick Forster, Fabian Kunze, Marc Roth
The weak call-by-value λ-calculus is reasonable for both time and space. Proc. ACM Program. Lang. 4 (POPL) (2020)
Marc Roth, Johannes Schmitt, Philip Wellnitz
Counting Small Induced Subgraphs Satisfying Monotone Properties. FOCS (2020)
Marc Roth, Johannes Schmitt
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. Algorithmica 82 (8) (2020)
Marc Roth, Philip Wellnitz
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory. SODA (2020)
Julian Dörfler, Marc Roth, Johannes Schmitt, Philip Wellnitz
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness. MFCS (2019)
Yannick Forster, Fabian Kunze, Marc Roth
The Weak Call-By-Value λ-Calculus is Reasonable for Both Time and Space. CoRR (2019)
Holger Dell, Marc Roth, Philip Wellnitz
Counting Answers to Existential Questions. ICALP (2019)
Julian Dörfler, Marc Roth, Johannes Schmitt, Philip Wellnitz
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness. CoRR (2019)
Cornelius Brand, Holger Dell, Marc Roth
Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP. Algorithmica 81 (2) (2019)
Holger Dell, Marc Roth, Philip Wellnitz
Counting Answers to Existential Questions. CoRR (2019)
Marc Roth, Philip Wellnitz
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory. CoRR (2019)
Radu Curticapean, Holger Dell, Marc Roth
Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes. Theory Comput. Syst. 63 (5) (2019)
Marc Roth, Johannes Schmitt
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. IPEC (2018)
Marc Roth, Johannes Schmitt
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. CoRR (2018)
Radu Curticapean, Holger Dell, Marc Roth
Counting edge-injective homomorphisms and matchings on restricted graph classes. CoRR (2017)
Radu Curticapean, Holger Dell, Marc Roth
Counting Edge-Injective Homomorphisms and Matchings on Restricted Graph Classes. STACS (2017)
Cornelius Brand, Marc Roth
Parameterized Counting of Trees, Forests and Matroid Bases. CSR (2017)
Marc Roth
Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices. ESA (2017)
Marc Roth
Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices. CoRR (2017)
Cornelius Brand, Marc Roth
Parameterized counting of trees, forests and matroid bases. CoRR (2016)
Cornelius Brand, Holger Dell, Marc Roth
Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP. IPEC (2016)
Cornelius Brand, Holger Dell, Marc Roth
Fine-grained dichotomies for the Tutte plane and Boolean #CSP. CoRR (2016)