scientific article; zbMATH DE number 6783503

zbMath1373.68256MaRDI QIDQ5365150

Pinyan Lu, Jin-Yi Cai, Mingji Xia

Publication date: 29 September 2017

Full work available at URL: http://dl.acm.org/citation.cfm?id=2133168

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (16)

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation ⋮ Unnamed Item ⋮ The computational complexity of Holant problems on 3-regular graphs ⋮ Holographic algorithms beyond matchgates ⋮ Complexity classification of the six-vertex model ⋮ A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs ⋮ Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS ⋮ On the Complexity of Holant Problems ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ The complexity of approximating conservative counting CSPs ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures

This page was built for publication: