Publications: Dr Marc Roth

Goldberg LA, Roth M, Schwarz T ( 2024 ) . Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process . Theoretical Computer Science

Bressan M, Ann Goldberg L, Meeks K, Roth M ( 2024 ) . Counting Subgraphs in Somewhere Dense Graphs . SIAM Journal on Computing vol. 53 , ( 5 ) 1409 - 1438 .

Focke J, Goldberg LA, Roth M, Živný S ( 2024 ) . Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations . ACM Transactions on Algorithms

Goebel A, Goldberg LA, Roth M ( 2024 ) . The Weisfeiler-Leman Dimension of Conjunctive Queries . Conference: Principles of Database Systems (PODS 2024)

Focke J, Roth M ( 2024 ) . Counting Small Induced Subgraphs with Hereditary Properties . SIAM Journal on Computing vol. 53 , ( 2 ) 189 - 220 .

Goldberg LA, Roth M ( 2023 ) . Parameterised and Fine-Grained Subgraph Counting, Modulo 2 . Algorithmica vol. 86 , ( 4 ) 944 - 1005 .

Goldberg LA, Roth M ( 2023 ) . Parameterised and Fine-Grained Subgraph Counting, Modulo 2 . Leibniz International Proceedings in Informatics, LIPIcs . Conference: ICALP 2023 vol. 261 ,

Bressan M, Lanzinger M, Roth M ( 2023 ) . The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree . Conference: Proceedings of the 55th Annual ACM Symposium on Theory of Computing542 - 552 .

Peyerimhoff N, Roth M, Schmitt J, Stix J, Vdovina A, Wellnitz P ( 2023 ) . Parameterized Counting and Cayley Graph Expanders . SIAM Journal on Discrete Mathematics vol. 37 , ( 2 ) 405 - 486 .

Bressan M, Goldberg LA, Meeks K, Roth M ( 2023 ) . Counting Subgraphs in Somewhere Dense Graphs . Leibniz International Proceedings in Informatics, LIPIcs vol. 251 ,

Focke J, Goldberg LA, Roth M, Zivný S ( 2022 ) . Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations . Conference: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems315 - 324 .

Focke J, Roth M ( 2022 ) . Counting small induced subgraphs with hereditary properties . Conference: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing1543 - 1551 .

Bressan M, Roth M ( 2022 ) . Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies . Conference: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) vol. 00 , 276 - 285 .

Dörfler J, Roth M, Schmitt J, Wellnitz P ( 2021 ) . Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness . Algorithmica vol. 84 , ( 2 ) 379 - 404 .

Focke J, Goldberg LA, Roth M, Živný S ( 2021 ) . Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2 . SIAM Journal on Discrete Mathematics vol. 35 , ( 4 ) 2749 - 2814 .

Peyerimhoff N, Roth M, Schmitt J, Stix J, Vdovina A ( 2021 ) . Parameterized (Modular) Counting and Cayley Graph Expanders . Leibniz International Proceedings in Informatics, LIPIcs . Conference: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) vol. 202 ,

Roth M, Schmitt J, Wellnitz P ( 2021 ) . Detecting and counting small subgraphs, and evaluating a parameterized tutte polynomial: Lower bounds via toroidal grids and cayley graph expanders . Leibniz International Proceedings in Informatics, LIPIcs . Conference: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) vol. 198 ,

Roth M ( 2021 ) . Parameterized Counting of Partially Injective Homomorphisms . Algorithmica vol. 83 , ( 6 ) 1829 - 1860 .

Roth M, Schmitt J, Wellnitz P ( 2020 ) . Counting Small Induced Subgraphs Satisfying Monotone Properties . Conference: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) vol. 00 , 1356 - 1367 .

Roth M, Schmitt J ( 2020 ) . Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness . Algorithmica vol. 82 , ( 8 ) 2267 - 2291 .

Roth M, Wellnitz P ( 2020 ) . Counting and finding homomorphisms is universal for parameterized complexity theory . Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms . vol. 2020-January , 2161 - 2180 .

Forster Y, Kunze F, Roth M ( 2019 ) . The weak call-by-value λ-calculus is reasonable for both time and space . Proceedings of the ACM on Programming Languages vol. 4 , ( POPL ) 1 - 23 .

Dörfler J, Roth M, Schmitt J, Wellnitz P ( 2019 ) . Counting induced subgraphs: An algebraic approach to #W[1]-hardness . Leibniz International Proceedings in Informatics, LIPIcs . vol. 138 ,

Dell H, Roth M, Wellnitz P ( 2019 ) . Counting answers to existential questions . Leibniz International Proceedings in Informatics, LIPIcs . vol. 132 ,

Roth M, Schmitt J ( 2019 ) . Counting induced subgraphs: A topological approach to #W[1]-hardness . Leibniz International Proceedings in Informatics, LIPIcs . vol. 115 ,

Curticapean R, Dell H, Roth M ( 2018 ) . Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes . Theory of Computing Systems vol. 63 , ( 5 ) 987 - 1026 .

Brand C, Dell H, Roth M ( 2018 ) . Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP . Algorithmica vol. 81 , ( 2 ) 541 - 556 .

Roth M ( 2017 ) . Counting restricted homomorphisms via möbius inversion over matroid lattices . Leibniz International Proceedings in Informatics, LIPIcs . vol. 87 ,

Brand C, Roth M ( 2017 ) . Parameterized Counting of Trees, Forests and Matroid Bases . Lecture Notes in Computer Science . vol. 10304 , 85 - 98 .

Curticapean R, Dell H, Roth M ( 2017 ) . Counting edge-injective homomorphisms and matchings on restricted graph classes . Leibniz International Proceedings in Informatics, LIPIcs . vol. 66 ,

Brand C, Dell H, Roth M ( 2017 ) . Fine-grained dichotomies for the Tutte plane and Boolean #CSP . Leibniz International Proceedings in Informatics, LIPIcs . vol. 63 ,