The Complexity of the Counting Constraint Satisfaction Problem
From MaRDI portal
Publication:3521956
DOI10.1007/978-3-540-70575-8_53zbMath1153.68386OpenAlexW1559445597MaRDI QIDQ3521956
Publication date: 28 August 2008
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.642.8196
Related Items (22)
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ The complexity of weighted Boolean \#CSP with mixed signs ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits ⋮ Holographic reduction, interpolation and hardness ⋮ Counting List Matrix Partitions of Graphs ⋮ The complexity of complex weighted Boolean \#CSP ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ Enumerating homomorphisms ⋮ The complexity of weighted and unweighted \(\#\)CSP ⋮ Generalized counting constraint satisfaction problems with determinantal circuits ⋮ A collapse theorem for holographic algorithms with matchgates on domain size at most 4 ⋮ Progress in Complexity of Counting Problems ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ An approximation trichotomy for Boolean \#CSP ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ The complexity of approximating conservative counting CSPs ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights ⋮ Classical simulation of quantum circuits by half Gauss sums
This page was built for publication: The Complexity of the Counting Constraint Satisfaction Problem
