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 Fundamentals of AI and Computational Theory
Publications of specific relevance to the Centre for Fundamentals of AI and Computational Theory2024
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran processGoldberg LA Roth M Schwarz T
Theoretical Computer Science, Elsevier
12-11-2024
Counting Subgraphs in Somewhere Dense GraphsBressan M Ann Goldberg L
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
Acm Transactions on Algorithms, Association For Computing Machinery (Acm)
23-08-2024
The Weisfeiler-Leman Dimension of Conjunctive QueriesGoebel A Goldberg LA Roth M
Principles of Database Systems (PODS 2024).
14-05-2024
Counting Small Induced Subgraphs with Hereditary PropertiesFocke J 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 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
Proceedings of the 55th Annual ACM Symposium on Theory of Computing., 542-552.
02-06-2023
Parameterized Counting and Cayley Graph ExpandersPeyerimhoff N Schmitt J Stix J Vdovina A
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
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
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing., 1543-1551.
09-06-2022
Counting Small Induced Subgraphs Satisfying Monotone PropertiesRoth M Schmitt J Wellnitz P
Siam Journal on Computing, Society For Industrial & Applied Mathematics (Siam), focs20-139-focs20-174-focs20-139-focs20-174.
11-04-2022
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity DichotomiesBressan 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 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 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
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 Ž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 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 Schmitt J
Algorithmica, Springer Nature vol. 82 (8), 2267-2291.
22-01-2020
Counting and finding homomorphisms is universal for parameterized complexity theoryRoth M 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
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
Leibniz International Proceedings in Informatics Lipics. vol. 138
01-08-2019
Counting answers to existential questionsDell H Roth M
Leibniz International Proceedings in Informatics Lipics. vol. 132
01-07-2019
Counting induced subgraphs: A topological approach to #W[1]-hardnessRoth M 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
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 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 Roth M
Leibniz International Proceedings in Informatics Lipics. vol. 66
01-03-2017
Fine-grained dichotomies for the Tutte plane and Boolean #CSPBrand C Roth M
Leibniz International Proceedings in Informatics Lipics. vol. 63
01-02-2017
Parameterized Counting of Trees, Forests and Matroid BasesBrand C Roth M
Lecture Notes in Computer Science. vol. 10304, 85-98.
01-01-2017
Research Group
PhD Students
- Madhu Krishnakumar
Motif Counting in Higher Order Structures
News
No news items found.