The complexity of approximating bounded-degree Boolean \#CSP

DOI10.4230/LIPICS.STACS.2010.2466MaRDI QIDQ3113760zbMATH OpenOpenAlexFDO

Authors Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_27ac.html

zbMATH Keywords

approximation algorithmsBoolean constraint satisfaction problemcountinggeneralized satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• scientific article; zbMATH DE number 7204479
• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• A trichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs

Cited in

(17)

• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• A trichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• Approximating Bounded Occurrence Ordering CSPs
• The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
• The complexity of weighted and unweighted \(\#\)CSP
• A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
• scientific article; zbMATH DE number 7204479 (Why is no real title available?)
• Approximate counting via correlation decay in spin systems
• Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
• A characterization of approximability for biased CSPs
• Bounded degree nonnegative counting CSP
• Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
• An approximation trichotomy for Boolean \#CSP

This page was built for publication: The complexity of approximating bounded-degree Boolean \#CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3113760)