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 algorithmscountinggeneralized satisfiabilityBoolean constraint satisfaction problem

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

(16)

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

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)