The complexity of approximating bounded-degree Boolean \(\#\)CSP
type: Item
instance of: scholarly article
title: The complexity of approximating bounded-degree Boolean \(\#\)CSP
zbMATH Open document ID: 1282.68136
author: Leslie Ann Goldberg
author: Markus Jalsenius
author: David Richerby
author: Martin Dyer
published in: Information and Computation
publication date: 2013-01-17T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6126525
zbMATH Keywords: counting constraint satisfaction problem
zbMATH Keywords: CSP
zbMATH Keywords: approximation algorithm
zbMATH Keywords: complexity
Wikidata QID: Q56323824
MaRDI profile type: Publication
full work available at URL: j.ic.2011.12.007
OpenAlex ID: W1966841310
cites work: On the Approximation Complexity Hierarchy
cites work: Q5501802
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: The Complexity of the Counting Constraint Satisfaction Problem
cites work: Holant problems and counting CSP
cites work: A unified theory of structural tractability for constraint satisfaction problems
cites work: Q4385531
cites work: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
cites work: Complexity of generalized satisfiability counting problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Mathematical Foundations of Computer Science 2003
cites work: Tree clustering for constraint networks
cites work: Counting \(H-\)colorings of partial \(k-\)trees
cites work: On Counting Independent Sets in Sparse Graphs
cites work: The relative complexity of approximate counting problems
cites work: The Complexity of Weighted Boolean #CSP
cites work: An approximation trichotomy for Boolean \#CSP
cites work: On counting homomorphisms to directed acyclic graphs
cites work: On Markov Chains for Independent Sets
cites work: Corrigendum: The complexity of counting graph homomorphisms
cites work: An effective dichotomy for the counting constraint satisfaction problem
cites work: Fanout limitations on constraint systems
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: On the complexity of H-coloring
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: Q2957449
cites work: Conjunctive-query containment and constraint satisfaction
cites work: On the Structure of Polynomial Time Reducibility
cites work: Fast convergence of the Glauber dynamics for sampling independent sets
cites work: Networks of constraints: Fundamental properties and applications to picture processing
cites work: The complexity of satisfiability problems
cites work: Q4139697
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Counting independent sets up to the tree threshold
cites work: Q3140234
DOI: 10.1016/J.IC.2011.12.007
description: scientific article; zbMATH DE number 6126525