An approximation trichotomy for Boolean \#CSP

DOI10.1016/J.JCSS.2009.08.003zbMATH Open1201.68154OpenAlexW1964923287WikidataQ56323828 ScholiaQ56323828MaRDI QIDQ972385FDOQ972385

Leslie Ann Goldberg, Mark Jerrum, Martin Dyer

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

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
• Approximate counting for complex-weighted Boolean constraint satisfaction problems

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Random generation of combinatorial structures from a uniform distribution
• The relative complexity of approximate counting problems
• The complexity of partition functions
• Complexity classifications of Boolean constraint satisfaction problems
• 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
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Title not available (Why is that?)
• The Complexity of the Counting Constraint Satisfaction Problem
• Complexity of generalized satisfiability counting problems
• Probability and Computing
• Structure identification of Boolean relations and plain bases for co-clones
• Title not available (Why is that?)
• Bases for Boolean co-clones

Cited In (33)

• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• The complexity of weighted and unweighted \(\#\)CSP
• A graph polynomial for independent sets of bipartite graphs
• Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
• Approximate counting for complex-weighted Boolean constraint satisfaction problems
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• On classifying continuous constraint satisfaction problems
• Counting Constraint Satisfaction Problems.
• Approximately counting paths and cycles in a graph
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Every 2-CSP allows nontrivial approximation
• The complexity of weighted Boolean \#CSP with mixed signs
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Counting of Teams in First-Order Team Logics
• Approximate Counting via Correlation Decay in Spin Systems
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
• The complexity of approximating conservative counting CSPs
• Title not available (Why is that?)
• Parameterized counting of partially injective homomorphisms
• Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems
• Title not available (Why is that?)
• Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
• An FPTAS for the hardcore model on random regular bipartite graphs
• A characterization of approximability for biased CSPs
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Title not available (Why is that?)
• Boolean max-co-clones
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• On Planar Boolean CSP
• The Complexity of Approximately Counting Tree Homomorphisms
• The complexity of approximating bounded-degree Boolean \(\#\)CSP

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)