79 citations · 95 across the 6 of their papers we have counts for
7 papers
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
Albert Atserias, Johannes Klaus Fichte, Marc Thurley
We offer a new understanding of some aspects of practical SAT-solvers that are based on DPLL with unit-clause propagation, clause-learning, and restarts. We do so by analyzing a co…
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…
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
Alistair Sinclair, Piyush Srivastava, Marc Thurley
In a seminal paper (Weitz, 2006), Weitz gave a deterministic fully polynomial approximation scheme for count- ing exponentially weighted independent sets (equivalently, approximati…
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…
The Complexity of Partition Functions on Hermitian Matrices
Marc Thurley
Partition functions of certain classes of "spin glass" models in statistical physics show strong connections to combinatorial graph invariants. Also known as homomorphism functions…