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
Publications of specific relevance to the Centre for Fundamental Computer Science2024
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran processGoldberg LA, Roth M and Schwarz T
Theoretical Computer Science, Elsevier
12-11-2024
Counting Subgraphs in Somewhere Dense GraphsBressan M, Ann Goldberg L, Meeks K and Roth M
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam) vol. 53 (5), 1409-1438.
27-09-2024
Approximately Counting Answers to Conjunctive Queries with Disequalities and NegationsFocke J, Goldberg LA, Roth M and Živný S
Acm Transactions on Algorithms, Association For Computing Machinery (Acm)
23-08-2024
The Weisfeiler-Leman Dimension of Conjunctive QueriesGoebel A, Goldberg LA and Roth M
Principles of Database Systems (PODS 2024).
14-05-2024
Counting Small Induced Subgraphs with Hereditary PropertiesFocke J and Roth M
Siam Journal on Computing, Society For Industrial and Applied Mathematics vol. 53 (2), 189-220.
12-03-2024
2023
Parameterised and Fine-Grained Subgraph Counting, Modulo 2Goldberg LA and Roth M
Algorithmica, Springer vol. 86 (4), 944-1005.
02-11-2023
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the OutdegreeBressan M, Lanzinger M and Roth M
Proceedings of the 55th Annual ACM Symposium on Theory of Computing., 542-552.
02-06-2023
Parameterized Counting and Cayley Graph ExpandersPeyerimhoff N, Roth M, Schmitt J, Stix J, Vdovina A and Wellnitz P
Siam Journal on Discrete Mathematics, Society For Industrial & Applied Mathematics (Siam) vol. 37 (2), 405-486.
26-04-2023
2022
Approximately Counting Answers to Conjunctive Queries with Disequalities and NegationsFocke J, Goldberg LA, Roth M and Zivný S
Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems., 315-324.
12-06-2022
Counting small induced subgraphs with hereditary propertiesFocke J and Roth M
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing., 1543-1551.
09-06-2022
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity DichotomiesBressan M and Roth M
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). vol. 00, 276-285.
10-02-2022
2021
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-HardnessDörfler J, Roth M, Schmitt J and Wellnitz P
Algorithmica, Springer Nature vol. 84 (2), 379-404.
07-12-2021
Parameterized (Modular) Counting and Cayley Graph ExpandersPeyerimhoff N, Roth M, Schmitt J, Stix J and Vdovina A
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). vol. 202
01-08-2021
Detecting and counting small subgraphs, and evaluating a parameterized tutte polynomial: Lower bounds via toroidal grids and cayley graph expandersRoth M, Schmitt J and Wellnitz P
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). vol. 198
01-07-2021
Parameterized Counting of Partially Injective HomomorphismsRoth M
Algorithmica, Springer Nature vol. 83 (6), 1829-1860.
11-03-2021
Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2Focke J, Goldberg LA, Roth M and Živný S
Siam Journal on Discrete Mathematics, Society For Industrial & Applied Mathematics (Siam) vol. 35 (4), 2749-2814.
01-01-2021
2020
Counting Small Induced Subgraphs Satisfying Monotone PropertiesRoth M, Schmitt J and Wellnitz P
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). vol. 00, 1356-1367.
19-11-2020
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardnessRoth M and Schmitt J
Algorithmica, Springer Nature vol. 82 (8), 2267-2291.
22-01-2020
Counting and finding homomorphisms is universal for parameterized complexity theoryRoth M and Wellnitz P
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. vol. 2020-January, 2161-2180.
01-01-2020
2019
The weak call-by-value λ-calculus is reasonable for both time and spaceForster Y, Kunze F and Roth M
Proceedings of The Acm on Programming Languages, Association For Computing Machinery (Acm) vol. 4 (POPL), 1-23.
20-12-2019
Counting induced subgraphs: An algebraic approach to #W[1]-hardnessDörfler J, Roth M, Schmitt J and Wellnitz P
Leibniz International Proceedings in Informatics, LIPIcs. vol. 138
01-08-2019
Counting answers to existential questionsDell H, Roth M and Wellnitz P
Leibniz International Proceedings in Informatics, LIPIcs. vol. 132
01-07-2019
Counting induced subgraphs: A topological approach to #W[1]-hardnessRoth M and Schmitt J
Leibniz International Proceedings in Informatics, LIPIcs. vol. 115
01-01-2019
2018
Counting Edge-injective Homomorphisms and Matchings on Restricted Graph ClassesCurticapean R, Dell H and Roth M
Theory of Computing Systems, Springer Nature vol. 63 (5), 987-1026.
31-10-2018
Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSPBrand C, Dell H and Roth M
Algorithmica, Springer Nature vol. 81 (2), 541-556.
22-06-2018
2017
Counting restricted homomorphisms via möbius inversion over matroid latticesRoth M
Leibniz International Proceedings in Informatics, LIPIcs. vol. 87
01-09-2017
Counting edge-injective homomorphisms and matchings on restricted graph classesCurticapean R, Dell H and Roth M
Leibniz International Proceedings in Informatics, LIPIcs. vol. 66
01-03-2017
Fine-grained dichotomies for the Tutte plane and Boolean #CSPBrand C, Dell H and Roth M
Leibniz International Proceedings in Informatics, LIPIcs. vol. 63
01-02-2017
Parameterized Counting of Trees, Forests and Matroid BasesBrand C and Roth M
Lecture Notes in Computer Science. vol. 10304, 85-98.
01-01-2017