Holographic algorithm with matchgates is universal for planar #CSP over boolean domain

DOI10.1145/3055399.3055405zbMath1369.68233arXiv1603.07046OpenAlexW2311858305MaRDI QIDQ4978028

Zhiguo Fu, Jin-Yi Cai

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1603.07046

zbMATH Keywords

holographic reductionmatchgatesplanar counting constraint satisfaction problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (8)

On blockwise symmetric matchgate signatures and higher domain \#CSP ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation ⋮ A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory ⋮ Unnamed Item ⋮ A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints

This page was built for publication: Holographic algorithm with matchgates is universal for planar #CSP over boolean domain