Skip to main content
Research
  1. Queen Mary University of London
  2. Research
  3. Publications

Publications: Dr Marc Roth

Back to Search
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
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 .
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 ,
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 .
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 .
Dell H, Roth M, Wellnitz P ( 2019 ) . Counting answers to existential questions . Leibniz International Proceedings in Informatics, LIPIcs . vol. 132 ,
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 ,
Back to Search