An approximation trichotomy for Boolean \#CSP
type: Item
instance of: scholarly article
title: An approximation trichotomy for Boolean \#CSP
zbMATH Open document ID: 1201.68154
author: Martin Dyer
author: Leslie Ann Goldberg
author: Mark Jerrum
published in: Journal of Computer and System Sciences
publication date: 2010-05-25T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 5711904
zbMATH Keywords: approximation algorithms
zbMATH Keywords: combinatorial enumeration
zbMATH Keywords: computational complexity
zbMATH Keywords: constraint satisfaction problems
MaRDI profile type: Publication
full work available at URL: j.jcss.2009.08.003
OpenAlex ID: W1964923287
Wikidata QID: Q56323828
cites work: Bases for Boolean co-clones
cites work: The Complexity of the Counting Constraint Satisfaction Problem
cites work: Towards a dichotomy theorem for the counting constraint satisfaction problem
cites work: The complexity of partition functions
cites work: Complexity of generalized satisfiability counting problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Structure identification of Boolean relations and plain bases for co-clones
cites work: The relative complexity of approximate counting problems
cites work: The Complexity of Weighted Boolean #CSP
cites work: Q4828516
cites work: Q4521549
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: On the Structure of Polynomial Time Reducibility
cites work: Probability and Computing
cites work: Q3221403
cites work: Q3184605
cites work: The complexity of satisfiability problems
DOI: 10.1016/J.JCSS.2009.08.003
description: scientific article; zbMATH DE number 5711904