Holant problems and counting CSP

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

zbMATH Keywords

CSPpolynomial interpolationHolant problemholographic reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (37)

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

This page was built for publication: Holant problems and counting CSP