Dichotomy for Holant Problems with a Function on Domain Size 3
From MaRDI portal
Publication:5741802
DOI10.1137/1.9781611973105.93zbMath1421.68065arXiv1207.2354OpenAlexW2950942956MaRDI QIDQ5741802
Jin-Yi Cai, Pinyan Lu, Mingji Xia
Publication date: 15 May 2019
Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.2354
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
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 ⋮ Zeros and approximations of holant polynomials on the complex plane ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Holographic algorithms beyond matchgates ⋮ On the Complexity of Holant Problems ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ The complexity of counting \(\mathrm{CSP}^d\)
