Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems
We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language Γ and a degree bound Δ, we study the complexity of #CSPΔ(Γ), which is the problem of counting satisfying assignments to CSP instance...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
European Association for Theoretical Computer
2017
|