Publications (32)
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
Marco Bressan, Matthias Lanzinger, Marc Roth
We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs and , count the number of copies of in .…
Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler--Leman and Hypertree Width
Panagiotis Aivasiliotis, Andreas Göbel, Matthias Lanzinger +1
The Weisfeiler--Leman (WL) algorithm is one of the most influential heuristics for the graph isomorphism problem. The expressive power of WL has been extensively studied in the con…
Parameterized counting of trees, forests and matroid bases
Cornelius Brand, Marc Roth
We investigate the complexity of counting trees, forests and bases of matroids from a parameterized point of view. It turns out that the problems of computing the number of trees a…
Parameterised Holant Problems
Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth +1
We investigate the complexity of parameterised holant problems p- for families of signatures . The parameterised holant framework was int…
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the complexity of approximating the number of answers to a small query in a large database . We establish an exhaustive classification into tractable and…
The Weak Call-By-Value λ-Calculus is Reasonable for Both Time and Space
Yannick Forster, Fabian Kunze, Marc Roth
We study the weak call-by-value -calculus as a model for computational complexity theory and establish the natural measures for time and space -- the number of beta-reductions…
Counting Answers to Existential Questions
Holger Dell, Marc Roth, Philip Wellnitz
Conjunctive queries select and are expected to return certain tuples from a relational database. We study the potentially easier problem of counting all selected tuples, rather tha…
Fine-grained dichotomies for the Tutte plane and Boolean #CSP
Cornelius Brand, Holger Dell, Marc Roth
Jaeger, Vertigan, and Welsh [15] proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the rema…
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem…
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
Julian Dörfler, Marc Roth, Johannes Schmitt +1
We study the problem #IndSub(P) of counting all induced subgraphs of size k in a graph G that satisfy the property P. This problem was introduced by Jerrum and Meeks and shown to b…
Parameterized (Modular) Counting and Cayley Graph Expanders
Norbert Peyerimhoff, Marc Roth, Johannes Schmitt +2
We study the problem of counting -edge subgraphs satisfying a given graph property in a large host graph . Building upon the breakthrough result…
Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders
Marc Roth, Johannes Schmitt, Philip Wellnitz
Given a graph property , we consider the problem , where the input is a pair of a graph and a positive integer , and the task is to decide whether…
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
Marco Bressan, Marc Roth
We study the problems of counting the homomorphisms, counting the copies, and counting the induced copies of a -vertex graph in a -degenerate -vertex graph . Our ma…
Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
Marc Roth
We present a framework for the complexity classification of parameterized counting problems that can be formulated as the summation over the numbers of homomorphisms from small pat…
Humanity's Last Exam
Long Phan, Alice Gatti, Ziwen Han +1144
Benchmarks are important tools for tracking the rapid advancements in large language model (LLM) capabilities. However, benchmarks are not keeping pace in difficulty: LLMs now achi…
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
Marc Roth, Philip Wellnitz
Counting homomorphisms from a graph into another graph is a fundamental problem of (parameterized) counting complexity theory. In this work, we study the case where \emph{b…
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness
Marc Roth, Johannes Schmitt
We investigate the problem of counting all induced subgraphs of size in a graph that satisfy a given property . This continues the work of Jerru…
The Science Performance of JWST as Characterized in Commissioning
Jane Rigby, Marshall Perrin, Michael McElwain +623
This paper characterizes the actual science performance of the James Webb Space Telescope (JWST), as determined from the six month commissioning period. We summarize the performanc…
Counting Small Induced Subgraphs Satisfying Monotone Properties
Marc Roth, Johannes Schmitt, Philip Wellnitz
Given a graph property , the problem asks, on input a graph and a positive integer , to compute the number of induced subgraphs of size in $G…
The Parametrised Complexity of Counting Small Sub-Hypergraphs
Marco Bressan, Julian Brinkmann, Holger Dell +2
Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has b…
The Parameterised Complexity of Temporal Motif Counting, and a Lovász-Style Isomorphism Theorem
Jayakrishnan Madathil, Kitty Meeks, Marc Roth
We study the structural expressivity and the parameterised complexity of counting homomorphisms from small temporal patterns to large temporal graphs. Here, a temporal pattern …
The Weisfeiler-Leman Dimension of Conjunctive Queries
Andreas Göbel, Leslie Ann Goldberg, Marc Roth
The Weisfeiler-Leman (WL) dimension of a graph parameter is the minimum such that, if and are indistinguishable by the -dimensional WL-algorithm then $f(G_1)…
COMPOSITE-Stem
Kyle Waters, Lucas Nuzzi, Tadhg Looram +20
AI agents hold growing promise for accelerating scientific discovery; yet, a lack of frontier evaluations hinders adoption into real workflows. Expert-written benchmarks have prove…
Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth
We study the complexity of the parameterised counting constraint satisfaction problem: given a set of constraints over a set of variables and a positive integer , how many ways…
Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process
Leslie Ann Goldberg, Marc Roth, Tassilo Constantin Schwarz
The multi-type Moran process is an evolutionary process on a connected graph in which each vertex has one of types and, in each step, a vertex is chosen to reproduce it…
Counting Small Induced Subgraphs with Hereditary Properties
Jacob Focke, Marc Roth
We study the computational complexity of the problem of counting -vertex induced subgraphs of a graph that satisfy a graph property . Our main resu…
IMProofBench: Benchmarking AI on Research-Level Mathematical Proof Generation
Johannes Schmitt, Gergely Bérczi, Jasper Dekoninck +57
As the mathematical capabilities of large language models (LLMs) improve, it becomes increasingly important to evaluate their performance on research-level tasks at the frontier of…
The Fine-Grained Complexity of Counting Hypergraph Motifs
Madhumitha Krishnakumar, Marc Roth
Introduced by Lee, Ko, and Shin (VLDB 2020), a hypergraph motif is a connected subhypergraph consisting of three hyperedges whose intersections satisfy a prescribed pattern. Such p…
Parameterised and Fine-grained Subgraph Counting, modulo
Leslie Ann Goldberg, Marc Roth
Given a class of graphs , the problem is defined as follows. The input is a graph together with an arbitrary graph…
Counting Homomorphisms to -minor-free Graphs, modulo 2
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the problem of computing the parity of the number of homomorphisms from an input graph to a fixed graph . Faben and Jerrum [ToC'15] introduced an explicit criterion…
Counting edge-injective homomorphisms and matchings on restricted graph classes
Radu Curticapean, Holger Dell, Marc Roth
We consider the -hard problem of counting all matchings with exactly edges in a given input graph ; we prove that it remains -hard on graph…
Counting Subgraphs in Somewhere Dense Graphs
Marco Bressan, Leslie Ann Goldberg, Kitty Meeks +1
We study the problems of counting copies and induced copies of a small pattern graph in a large host graph . Recent work fully classified the complexity of those problems ac…