5 citations · 5 across the 3 of their papers we have counts for
4 papers
An Approximation Algorithm for #k-SAT
Marc Thurley
We present a simple randomized algorithm that approximates the number of satisfying assignments of Boolean formulas in conjunctive normal form. To the best of our knowledge this is…
Computing hypergraph width measures exactly
Lukas Moll, Siamak Tazari, Marc Thurley
Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponenti…
Counting Homomorphisms and Partition Functions
Martin Grohe, Marc Thurley
Homomorphisms between relational structures are not only fundamental mathematical objects, but are also of great importance in an applied computational context. Indeed, constraint…
A complexity dichotomy for partition functions with mixed signs
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum +1
Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colourings or the nu…