Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
type: Item
instance of: scholarly article
title: Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
zbMATH Open document ID: 1356.68094
DOI: 10.1137/15M1032314
author: Jin-Yi Cai
author: Xi Chen
author: Pinyan Lu
published in: SIAM Journal on Computing
publication date: 2016-12-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/1012.5659
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6667473
zbMATH Keywords: constraint satisfaction problem
zbMATH Keywords: counting problems
zbMATH Keywords: complexity dichotomy
MaRDI profile type: Publication
arXiv ID: 1012.5659
cites work: Approximation resistant predicates from pairwise independence
cites work: A Simple Algorithm for Mal'tsev Constraints
cites work: The complexity of weighted and unweighted \(\#\)CSP
cites work: The complexity of partition functions
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: Towards a dichotomy theorem for the counting constraint satisfaction problem
cites work: Principles and Practice of Constraint Programming – CP 2003
cites work: Recent Results on the Algebraic Approach to the CSP
cites work: Q3934450
cites work: Complexity of counting CSP with complex weights
cites work: Graph homomorphisms with complex values: a dichotomy theorem
cites work: A complete dichotomy rises from the capture of vanishing signatures
cites work: From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
cites work: Holant problems and counting CSP
cites work: Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
cites work: Q5365150
cites work: Dichotomy for Holant Problems with a Function on Domain Size 3
cites work: Conditional Hardness for Approximate Coloring
cites work: On counting homomorphisms to directed acyclic graphs
cites work: Q4521549
cites work: An effective dichotomy for the counting constraint satisfaction problem
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Q3775604
cites work: A Complexity Dichotomy for Partition Functions with Mixed Signs
cites work: Some optimal inapproximability results
cites work: On the complexity of H-coloring
cites work: The structure of finite algebras
cites work: On the algebraic structure of combinatorial problems
cites work: Constraints, consistency and closure
cites work: Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
cites work: A new line of attack on the dichotomy conjecture
cites work: Algorithms in Algebraic Number Theory
cites work: Operations with structures
cites work: Q3549708
cites work: How to Round Any CSP
cites work: The complexity of satisfiability problems
cites work: CSP gaps and reductions in the lasserre hierarchy
cites work: Holographic Algorithms
OpenAlex ID: W2567588342
description: scientific article