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
\(\#\)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
