
Parameterized (Modular) Counting and Cayley Graph Expanders
We study the problem #EdgeSub(Φ) of counting kedge subgraphs satisfying...
read it

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
We study the complexity of approximating the number of answers to a smal...
read it

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...
read it

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 ...
read it

Counting Homomorphisms to K_4minorfree Graphs, modulo 2
We study the problem of computing the parity of the number of homomorphi...
read it

Counting Small Induced Subgraphs Satisfying Monotone Properties
Given a graph property Φ, the problem #𝖨𝗇𝖽𝖲𝗎𝖻(Φ) asks, on input a graph ...
read it

Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
Counting homomorphisms from a graph H into another graph G is a fundamen...
read it

Counting Induced Subgraphs: An Algebraic Approach to #W[1]hardness
We study the problem #IndSub(P) of counting all induced subgraphs of siz...
read it

The Weak CallByValue λCalculus is Reasonable for Both Time and Space
We study the weak callbyvalue λcalculus as a model for computational ...
read it

Counting Answers to Existential Questions
Conjunctive queries select and are expected to return certain tuples fro...
read it

Counting Induced Subgraphs: A Topological Approach to #W[1]hardness
We investigate the problem #IndSub(Φ) of counting all induced subgraphs ...
read it
Marc Roth
is this you? claim profile