Counting Constraint Satisfaction Problems.

DOI10.4230/DFU.Vol7.15301.205zbMath1482.68164OpenAlexW2592203159MaRDI QIDQ4993601

Mark R. Jerrum

Publication date: 15 June 2021

Full work available at URL: https://dblp.uni-trier.de/db/conf/dagstuhl/dfu7.html#Jerrum17

zbMATH Keywords

computational complexitypartition functionsapproximation algorithmsconstraint satisfaction problemscounting problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Computational aspects of satisfiability (68R07)

Cites Work

• Unnamed Item
• Unnamed Item
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• The complexity of complex weighted Boolean \#CSP
• Counting in two-spin models on \(d\)-regular graphs
• Boolean max-co-clones
• The complexity of approximating conservative counting CSPs
• The complexity of weighted Boolean \#CSP with mixed signs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Inapproximability of the Tutte polynomial
• Structure identification of Boolean relations and plain bases for co-clones
• On the counting complexity of propositional circumscription
• An approximation trichotomy for Boolean \#CSP
• On the hardness of sampling independent sets beyond the tree threshold
• NP is as easy as detecting unique solutions
• The relative complexity of approximate counting problems
• Complexity of generalized satisfiability counting problems
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• The complexity of planar Boolean \#CSP with complex weights
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• The complexity of partition functions
• Improved bounds for sampling colorings
• Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard
• The complexity of counting homomorphisms to cactus graphs modulo 2
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• The complexity of parity graph homomorphism: an initial investigation
• A complexity classification of spin systems with an external field
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• The Complexity of Ferromagnetic Two-spin Systems with External Fields
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Polynomial-Time Approximation Algorithms for the Ising Model
• On Counting Independent Sets in Sparse Graphs
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• The Complexity of Ferromagnetic Ising with Local Fields
• Counting Homomorphisms to Square-Free Graphs, Modulo 2
• Approximating the Partition Function of the Ferromagnetic Potts Model
• The Complexity of Weighted Boolean #CSP
• The Complexity of Enumeration and Reliability Problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The computational complexity of two‐state spin systems
• Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• Bi‐arc graphs and the complexity of list homomorphisms
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The expressibility of functions on the boolean domain, with applications to counting CSPs
• The complexity of the counting constraint satisfaction problem
• Complexity of counting CSP with complex weights
• A Simple Algorithm for Mal'tsev Constraints
• Correlation Decay up to Uniqueness in Spin Systems
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem