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
|
| _version_ | 1797060614194987008 |
|---|---|
| author | Galanis, A Goldberg, L Yang, K |
| author_facet | Galanis, A Goldberg, L Yang, K |
| author_sort | Galanis, A |
| collection | OXFORD |
| description | 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 instances with constraints from Γ and whose variables can appear at most Δ times. Our main result shows that: (i) if every function in Γ is affine, then #CSPΔ(Γ) is in FP for all Δ, (ii) otherwise, if every function in Γ is in a class called IM2, then for all sufficiently large Δ, #CSPΔ(Γ) is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large Δ, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSPΔ(Γ), even within an exponential factor. Our result extends previous results, which apply only in the so-called “conservative” case. A full version of the paper containing detailed proofs is available at http://arxiv.org/abs/1610.04055 and is attached as an appendix. Theorem-numbering here matches the full version. |
| first_indexed | 2024-03-06T20:19:34Z |
| format | Conference item |
| id | oxford-uuid:2d53495a-31e9-48b2-be44-0a4b1723cac0 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:19:34Z |
| publishDate | 2017 |
| publisher | European Association for Theoretical Computer |
| record_format | dspace |
| spelling | oxford-uuid:2d53495a-31e9-48b2-be44-0a4b1723cac02022-03-26T12:42:17ZApproximating partition functions of bounded- degree Boolean counting Constraint Satisfaction ProblemsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:2d53495a-31e9-48b2-be44-0a4b1723cac0Symplectic Elements at OxfordEuropean Association for Theoretical Computer2017Galanis, AGoldberg, LYang, KWe 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 instances with constraints from Γ and whose variables can appear at most Δ times. Our main result shows that: (i) if every function in Γ is affine, then #CSPΔ(Γ) is in FP for all Δ, (ii) otherwise, if every function in Γ is in a class called IM2, then for all sufficiently large Δ, #CSPΔ(Γ) is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large Δ, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSPΔ(Γ), even within an exponential factor. Our result extends previous results, which apply only in the so-called “conservative” case. A full version of the paper containing detailed proofs is available at http://arxiv.org/abs/1610.04055 and is attached as an appendix. Theorem-numbering here matches the full version. |
| spellingShingle | Galanis, A Goldberg, L Yang, K Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems |
| title | Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems |
| title_full | Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems |
| title_fullStr | Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems |
| title_full_unstemmed | Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems |
| title_short | Approximating partition functions of bounded- degree Boolean counting Constraint Satisfaction Problems |
| title_sort | approximating partition functions of bounded degree boolean counting constraint satisfaction problems |
| work_keys_str_mv | AT galanisa approximatingpartitionfunctionsofboundeddegreebooleancountingconstraintsatisfactionproblems AT goldbergl approximatingpartitionfunctionsofboundeddegreebooleancountingconstraintsatisfactionproblems AT yangk approximatingpartitionfunctionsofboundeddegreebooleancountingconstraintsatisfactionproblems |