An approximation trichotomy for Boolean \#CSP

DOI10.1016/j.jcss.2009.08.003zbMath1201.68154WikidataQ56323828 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 complexity; combinatorial enumeration; approximation algorithms; constraint satisfaction problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68W25: Approximation algorithms

Related Items

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

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