research
∙
03/14/2023
Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process
The multi-type Moran process is an evolutionary process on a connected g...
share
research
∙
01/04/2023
Parameterised and Fine-grained Subgraph Counting, modulo 2
Given a class of graphs ℋ, the problem ⊕𝖲𝗎𝖻(ℋ) is defined as follows. Th...
research
∙
11/03/2022
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
We study the fixed-parameter tractability of the following fundamental p...
research
∙
09/07/2022
Counting Subgraphs in Somewhere Dense Graphs
We study the problems of counting copies and induced copies of a small p...
research
∙
11/03/2021
Counting Small Induced Subgraphs with Hereditary Properties
We study the computational complexity of the problem #IndSub(Φ) of count...
research
∙
04/29/2021
Parameterized (Modular) Counting and Cayley Graph Expanders
We study the problem #EdgeSub(Φ) of counting k-edge subgraphs satisfying...
research
∙
03/23/2021
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
We study the complexity of approximating the number of answers to a smal...
research
∙
03/09/2021
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
We study the problems of counting the homomorphisms, counting the copies...
research
∙
11/06/2020
Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders
Given a graph property Φ, we consider the problem 𝙴𝚍𝚐𝚎𝚂𝚞𝚋(Φ), where the ...
research
∙
06/30/2020
Counting Homomorphisms to K_4-minor-free Graphs, modulo 2
We study the problem of computing the parity of the number of homomorphi...
research
∙
04/14/2020
Counting Small Induced Subgraphs Satisfying Monotone Properties
Given a graph property Φ, the problem #𝖨𝗇𝖽𝖲𝗎𝖻(Φ) asks, on input a graph ...
research
∙
07/08/2019
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
Counting homomorphisms from a graph H into another graph G is a fundamen...
research
∙
04/23/2019
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
We study the problem #IndSub(P) of counting all induced subgraphs of siz...
research
∙
02/20/2019
The Weak Call-By-Value λ-Calculus is Reasonable for Both Time and Space
We study the weak call-by-value λ-calculus as a model for computational ...
research
∙
02/13/2019
Counting Answers to Existential Questions
Conjunctive queries select and are expected to return certain tuples fro...
research
∙
07/05/2018