scientific article; zbMATH DE number 7204479

DOI10.4230/LIPICS.ICALP.2017.27MaRDI QIDQ5111357zbMATHFDO

Authors Andreas Galanis, Leslie Ann Goldberg, Kuan Yang

Publication date 27 May 2020

zbMATH Keywords

constraint satisfactionapproximate counting

Mathematics Subject Classification ID

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

Recommendations

• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• The complexity of approximating bounded-degree Boolean \#CSP
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• An approximation trichotomy for Boolean \#CSP
• The complexity of approximating conservative counting CSPs

Cited in

(7)

• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• The complexity of approximating bounded-degree Boolean \#CSP
• The complexity of approximating conservative counting CSPs
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• The complexity of approximating conservative counting CSPs
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• An FPTAS for the hardcore model on random regular bipartite graphs

This page was built for publication:

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