An approximation trichotomy for Boolean \#CSP

DOI10.1016/J.JCSS.2009.08.003MaRDI QIDQ972385zbMATH OpenOpenAlexWikidataFDO

Authors Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

Publication date 25 May 2010

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2009.08.003

zbMATH Keywords

computational complexityapproximation algorithmsconstraint satisfaction problemscombinatorial enumeration

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• 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
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• The complexity of approximating bounded-degree Boolean \#CSP

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Bases for Boolean co-clones
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of generalized satisfiability counting problems
• Handbook of constraint programming.
• On the Structure of Polynomial Time Reducibility
• Probability and Computing
• Random generation of combinatorial structures from a uniform distribution
• Structure identification of Boolean relations and plain bases for co-clones
• The Complexity of Weighted Boolean #CSP
• The Complexity of the Counting Constraint Satisfaction Problem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of partition functions
• The complexity of satisfiability problems
• The relative complexity of approximate counting problems
• Towards a dichotomy theorem for the counting constraint satisfaction problem

Cited in

(34)

• 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
• Counting restricted homomorphisms via Möbius inversion over matroid lattices
• Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
• A graph polynomial for independent sets of bipartite graphs
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Approximately counting paths and cycles in a graph
• On classifying continuous constraint satisfaction problems
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• The complexity of weighted Boolean \#CSP with mixed signs
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Every 2-CSP allows nontrivial approximation
• Counting of Teams in First-Order Team Logics
• A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• The complexity of approximating conservative counting CSPs
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• The complexity of approximating conservative counting CSPs
• scientific article; zbMATH DE number 6861969 (Why is no real title available?)
• Parameterized counting of partially injective homomorphisms
• Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems
• Approximate counting via correlation decay in spin systems
• Counting constraint satisfaction problems
• An FPTAS for the hardcore model on random regular bipartite graphs
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• A characterization of approximability for biased CSPs
• Counting of teams in first-order team logics
• The complexity of approximately counting tree homomorphisms
• Boolean max-co-clones
• scientific article; zbMATH DE number 7561704 (Why is no real title available?)
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• On Planar Boolean CSP
• Hardness of identity testing for restricted Boltzmann machines and Potts models

This page was built for publication: An approximation trichotomy for Boolean \#CSP

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