Complexity of Counting CSP with Complex Weights
From MaRDI portal
Publication:4640291
DOI10.1145/2822891zbMath1426.68114arXiv1111.2384OpenAlexW2626596188MaRDI QIDQ4640291
Publication date: 17 May 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1111.2384
Related Items
Perfect matchings, rank of connection tensors and graph homomorphisms ⋮ Zero-freeness and approximation of real Boolean Holant problems ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Approximability of the complementarily symmetric Holant problems on cubic graphs ⋮ A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory ⋮ Complexity classification of the eight-vertex model ⋮ Unnamed Item ⋮ 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 ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Unnamed Item ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ 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 ⋮ The complexity of counting \(\mathrm{CSP}^d\)