We show conditional lower bounds for well-studied# P-hard problems: The number of
satisfying assignments of a 2-CNF formula with n variables cannot be computed in time exp …

Partition functions, also known as homomorphism functions, form a rich family of graph
invariants that contain combinatorial invariants such as the number of k-colorings or the …

The deletion–contraction algorithm is perhapsthe most popular method for computing a host
of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in …

In this thesis, we study the parameterized complexity of counting problems, as introduced by
Flum and Grohe. This area mainly involves questions of the following kind: On inputs x with …

By now, we have a good understanding of how NP-hard problems become easier on graphs
of bounded treewidth and bounded cliquewidth: for various problems, matching upper …

K. Dohmen, A. Pönitz and P. Tittmann [K. Dohmen, A. Pönitz, P. Tittmann, A new two-
variable generalization of the chromatic polynomial, Discrete Mathematics and Theoretical …

We devise a framework for proving tight lower bounds under the counting exponential-time
hypothesis# ETH introduced by Dell et al.(2014)[18]. Our framework allows us to convert …

We outline a general theory of graph polynomials which covers all the examples we found in
the vast literature, in particular, the chromatic polynomial, various generalizations of the …

Inspired by the study of community structure in connection networks, we introduce the graph
polynomial Q (G; x, y), the bivariate generating function which counts the number of …

We consider the complexity of computing the determinant over arbitrary finite-dimensional
algebras. We first consider the case that A is fixed. In this case, we obtain the following …