Holant problems and counting CSP
From MaRDI portal
Publication:5172769
DOI10.1145/1536414.1536511zbMath1304.68067MaRDI 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
68Q25: Analysis of algorithms and problem complexity
Related Items
The Complexity of Boolean Holant Problems with Nonnegative Weights, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, On the Complexity of Holant Problems, Classification of a Class of Counting Problems Using Holographic Reductions, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, The Complexity of Symmetric Boolean Parity Holant Problems, Bipartite 3-regular counting problems with mixed signs, Bipartite 3-regular counting problems with mixed signs, Approximate Counting via Correlation Decay in Spin Systems, Perfect matchings, rank of connection tensors and graph homomorphisms, A dichotomy for real weighted Holant problems, \(\#\)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, Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions, The complexity of complex weighted Boolean \#CSP, The complexity of weighted and unweighted \(\#\)CSP, A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs, A computational proof of complexity of some restricted 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, The complexity of approximating conservative counting CSPs, Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits, On blockwise symmetric matchgate signatures and higher domain \#CSP, Zero-free regions of partition functions with applications to algorithms and graph limits, Holographic reduction, interpolation and hardness, Holographic algorithms by Fibonacci gates, The complexity of approximating bounded-degree Boolean \(\#\)CSP, From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems, The complexity of planar Boolean \#CSP with complex weights, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, The complexity of counting \(\mathrm{CSP}^d\), Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Progress in Complexity of Counting Problems, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
