An approximation trichotomy for Boolean \#CSP

DOI10.1016/j.jcss.2009.08.003zbMath1201.68154OpenAlexW1964923287WikidataQ56323828 ScholiaQ56323828MaRDI QIDQ972385

Leslie Ann Goldberg, Martin Dyer, Mark R. 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 complexitycombinatorial enumerationapproximation algorithmsconstraint satisfaction problems

Mathematics Subject Classification ID

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

Related Items

\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, The complexity of counting locally maximal satisfying assignments of Boolean CSPs, The complexity of weighted Boolean \#CSP with mixed signs, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, A Graph Polynomial for Independent Sets of Bipartite Graphs, An FPTAS for the hardcore model on random regular bipartite graphs, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, The Complexity of Approximately Counting Tree Homomorphisms, 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, A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs, Counting Constraint Satisfaction Problems., Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, Boolean max-co-clones, Approximately counting paths and cycles in a graph, Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems, Approximate counting for complex-weighted Boolean constraint satisfaction problems, Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems, Unnamed Item, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, Parameterized counting of partially injective homomorphisms, The complexity of approximating conservative counting CSPs, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin, Counting of Teams in First-Order Team Logics, Approximate Counting via Correlation Decay in Spin Systems, Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Structure identification of Boolean relations and plain bases for co-clones
• Bases for Boolean co-clones
• Random generation of combinatorial structures from a uniform distribution
• The relative complexity of approximate counting problems
• Complexity of generalized satisfiability counting problems
• The complexity of partition functions
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of the Counting Constraint Satisfaction Problem
• The Complexity of Weighted Boolean #CSP
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of satisfiability problems
• Probability and Computing