An Effective Dichotomy for the Counting Constraint Satisfaction Problem
From MaRDI portal
Publication:2848220
DOI10.1137/100811258zbMath1275.68077arXiv1003.3879OpenAlexW1991486497WikidataQ56323805 ScholiaQ56323805MaRDI QIDQ2848220
Publication date: 25 September 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1003.3879
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (32)
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ Zero-freeness and approximation of real Boolean Holant problems ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Counting List Matrix Partitions of Graphs ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ Unnamed Item ⋮ Approximability of the complementarily symmetric Holant problems on cubic graphs ⋮ Complexity classification of the eight-vertex model ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ Unnamed Item ⋮ Holographic algorithms beyond matchgates ⋮ Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS ⋮ Counting Constraint Satisfaction Problems. ⋮ A collapse theorem for holographic algorithms with matchgates on domain size at most 4 ⋮ Unnamed Item ⋮ THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ The complexity of approximating conservative counting CSPs ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems ⋮ Approximability of the eight-vertex model ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ The complexity of counting \(\mathrm{CSP}^d\) ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights ⋮ Unnamed Item
This page was built for publication: An Effective Dichotomy for the Counting Constraint Satisfaction Problem
