Holant problems and counting CSP
From MaRDI portal
Publication:5172769
DOI10.1145/1536414.1536511zbMath1304.68067OpenAlexW2012753562MaRDI QIDQ5172769
Pinyan Lu, Jin-Yi Cai, Mingji Xia
Publication date: 4 February 2015
Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1536414.1536511
Related Items
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, Perfect matchings, rank of connection tensors and graph homomorphisms, On blockwise symmetric matchgate signatures and higher domain \#CSP, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, Classification of a Class of Counting Problems Using Holographic Reductions, The Complexity of Boolean Holant Problems with Nonnegative Weights, Holographic reduction, interpolation and hardness, Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions, The complexity of complex weighted Boolean \#CSP, Holographic algorithms by Fibonacci gates, The complexity of approximating bounded-degree Boolean \(\#\)CSP, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, The complexity of weighted and unweighted \(\#\)CSP, The computational complexity of Holant problems on 3-regular graphs, A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs, On the Complexity of Holant Problems, Progress in Complexity of Counting Problems, Spin systems on \(k\)-regular graphs with complex edge functions, Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems, Approximate counting for complex-weighted Boolean constraint satisfaction problems, Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems, A computational proof of complexity of some restricted counting problems, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, The complexity of planar Boolean \#CSP with complex weights, Zero-free regions of partition functions with applications to algorithms and graph limits, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, The Complexity of Symmetric Boolean Parity Holant Problems, Bipartite 3-regular counting problems with mixed signs, The complexity of approximating conservative counting CSPs, Bipartite 3-regular counting problems with mixed signs, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Approximate Counting via Correlation Decay in Spin Systems, The complexity of counting \(\mathrm{CSP}^d\), A dichotomy for real weighted Holant problems
