Marc Roth

Orcid: 0000-0003-3159-9418

Affiliations:
  • University of Oxford, UK


According to our database1, Marc Roth authored at least 27 papers between 2017 and 2024.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Counting Small Induced Subgraphs with Hereditary Properties.
SIAM J. Comput., 2024

2023
Parameterized Counting and Cayley Graph Expanders.
SIAM J. Discret. Math., June, 2023

Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity.
CoRR, 2023

The Weisfeiler-Leman Dimension of Existential Conjunctive Queries.
CoRR, 2023

Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process.
CoRR, 2023

The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Counting Subgraphs in Somewhere Dense Graphs.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Parameterised and Fine-Grained Subgraph Counting, Modulo 2.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness.
Algorithmica, 2022

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.
Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

2021
Counting Homomorphisms to K<sub>4</sub>-Minor-Free Graphs, Modulo 2.
SIAM J. Discret. Math., 2021

Counting homomorphisms, subgraphs, and induced subgraphs in degenerate graphs: new hardness results and complete complexity classifications.
CoRR, 2021

Parameterized Counting of Partially Injective Homomorphisms.
Algorithmica, 2021

Counting Homomorphisms to <i>K</i><sub>4</sub>-minor-free Graphs, modulo 2.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Parameterized (Modular) Counting and Cayley Graph Expanders.
Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
The weak call-by-value λ-calculus is reasonable for both time and space.
Proc. ACM Program. Lang., 2020

Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness.
Algorithmica, 2020

Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Counting Small Induced Subgraphs Satisfying Monotone Properties.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
Counting problems on quantum graphs.
PhD thesis, 2019

Counting Edge-injective Homomorphisms and Matchings on Restricted Graph Classes.
Theory Comput. Syst., 2019

Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP.
Algorithmica, 2019

Counting Answers to Existential Questions.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2017
Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Parameterized Counting of Trees, Forests and Matroid Bases.
Proceedings of the Computer Science - Theory and Applications, 2017


  Loading...