Complexity of counting CSP with complex weights
From MaRDI portal
Publication:5415524
DOI10.1145/2213977.2214059zbMath1286.68182OpenAlexW2157384210WikidataQ56168971 ScholiaQ56168971MaRDI QIDQ5415524
Publication date: 13 May 2014
Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2213977.2214059
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (18)
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits ⋮ The complexity of complex weighted Boolean \#CSP ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ A finite-tame-wild trichotomy theorem for tensor diagrams ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory ⋮ Fine-grained dichotomies for the Tutte plane and Boolean \#CSP ⋮ Generalized counting constraint satisfaction problems with determinantal circuits ⋮ Counting Constraint Satisfaction Problems. ⋮ A collapse theorem for holographic algorithms with matchgates on domain size at most 4 ⋮ Lee-Yang theorems and the complexity of computing averages ⋮ The complexity of approximating conservative counting CSPs ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
This page was built for publication: Complexity of counting CSP with complex weights
