Dr Marc Roth
Lecturer in Theoretical Computer Science
School of Electronic Engineering and Computer Science
Queen Mary University of London
Queen Mary University of London
Research
graph theory, algorithmics, computational complexity theory, parameterised algorithms, fine-grained complexity theory, computational counting problems
Interests
Dr. Roth's research concerns graph theory, algorithmics, and computational complexity theory with a focus on pattern counting problems that appear in the analysis of large networks. In particular, he is interested in the multivariate and exact complexity of counting problems that are infeasible from the viewpoint of classical complexity theory.Publications of specific relevance to the Centre for Fundamental Computer Science
2024
Goldberg LA, Roth M and Schwarz T (2024). Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process. Theoretical Computer Science, Elsevier 12-11-2024
Bressan M, Ann Goldberg L, Meeks K and Roth M (2024). Counting Subgraphs in Somewhere Dense Graphs. SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM) vol. 53 (5), 1409-1438. 27-09-2024
Focke J, Goldberg LA, Roth M and Živný S (2024). Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. ACM Transactions on Algorithms, Association for Computing Machinery (ACM) 23-08-2024
Goebel A, Goldberg LA and Roth M (2024). The Weisfeiler-Leman Dimension of Conjunctive Queries. Principles of Database Systems (PODS 2024). 14-05-2024
Focke J and Roth M (2024). Counting Small Induced Subgraphs with Hereditary Properties. SIAM Journal on Computing, Society for Industrial and Applied Mathematics vol. 53 (2), 189-220. 12-03-2024
2023
Goldberg LA and Roth M (2023). Parameterised and Fine-Grained Subgraph Counting, Modulo 2. Algorithmica, Springer vol. 86 (4), 944-1005. 02-11-2023
Bressan M, Lanzinger M and Roth M (2023). The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree. Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 02-06-2023
Peyerimhoff N, Roth M, Schmitt J, Stix J, Vdovina A and Wellnitz P (2023). Parameterized Counting and Cayley Graph Expanders. SIAM Journal on Discrete Mathematics, Society for Industrial & Applied Mathematics (SIAM) vol. 37 (2), 405-486. 26-04-2023
2022
Focke J, Goldberg LA, Roth M and Zivný S (2022). Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 12-06-2022
Focke J and Roth M (2022). Counting small induced subgraphs with hereditary properties. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. 09-06-2022
Bressan M and Roth M (2022). Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 10-02-2022
2021
Dörfler J, Roth M, Schmitt J and Wellnitz P (2021). Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness. Algorithmica, Springer Nature vol. 84 (2), 379-404. 07-12-2021
Peyerimhoff N, Roth M, Schmitt J, Stix J and Vdovina A (2021). Parameterized (Modular) Counting and Cayley Graph Expanders. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). 01-08-2021
Roth M, Schmitt J and Wellnitz P (2021). Detecting and counting small subgraphs, and evaluating a parameterized tutte polynomial: Lower bounds via toroidal grids and cayley graph expanders. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). 01-07-2021
Roth M (2021). Parameterized Counting of Partially Injective Homomorphisms. Algorithmica, Springer Nature vol. 83 (6), 1829-1860. 11-03-2021
Focke J, Goldberg LA, Roth M and Živný S (2021). Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2. SIAM Journal on Discrete Mathematics, Society for Industrial & Applied Mathematics (SIAM) vol. 35 (4), 2749-2814. 01-01-2021
2020
Roth M, Schmitt J and Wellnitz P (2020). Counting Small Induced Subgraphs Satisfying Monotone Properties. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 19-11-2020
Roth M and Schmitt J (2020). Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. Algorithmica, Springer Nature vol. 82 (8), 2267-2291. 22-01-2020
Roth M and Wellnitz P (2020). Counting and finding homomorphisms is universal for parameterized complexity theory. 01-01-2020
2019
Forster Y, Kunze F and Roth M (2019). The weak call-by-value λ-calculus is reasonable for both time and space. Proceedings of the ACM on Programming Languages, Association for Computing Machinery (ACM) vol. 4 (POPL), 1-23. 20-12-2019
Dörfler J, Roth M, Schmitt J and Wellnitz P (2019). Counting induced subgraphs: An algebraic approach to #W[1]-hardness. 01-08-2019
Roth M and Schmitt J (2019). Counting induced subgraphs: A topological approach to #W[1]-hardness. 01-01-2019
2018
Curticapean R, Dell H and Roth M (2018). Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes. Theory of Computing Systems, Springer Nature vol. 63 (5), 987-1026. 31-10-2018
Brand C, Dell H and Roth M (2018). Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP. Algorithmica, Springer Nature vol. 81 (2), 541-556. 22-06-2018
2017
Roth M (2017). Counting restricted homomorphisms via möbius inversion over matroid lattices. 01-09-2017
Curticapean R, Dell H and Roth M (2017). Counting edge-injective homomorphisms and matchings on restricted graph classes. 01-03-2017
Brand C, Dell H and Roth M (2017). Fine-grained dichotomies for the Tutte plane and Boolean #CSP. 01-02-2017