scientific article

DOI10.4086/toc.2014.v010a007zbMath1342.68156arXiv1303.6729OpenAlexW4252625889MaRDI QIDQ3191606

Aaron Gorenstein, Jin-Yi Cai

Publication date: 6 October 2014

Published in: Theory of Computing (Search for Journal in Brave)

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

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

zbMATH Keywords

Pfaffian orientationcomplexity theorymatchgates

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (13)

Some observations on holographic algorithms ⋮ On blockwise symmetric matchgate signatures and higher domain \#CSP ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Holographic algorithms on domains of general size ⋮ A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory ⋮ Undirected determinant and its complexity ⋮ Holographic algorithms beyond matchgates ⋮ A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory ⋮ A collapse theorem for holographic algorithms with matchgates on domain size at most 4 ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints ⋮ Functional clones and expressibility of partition functions

Cites Work

• Signature theory in holographic algorithms
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Dimer problem in statistical mechanics-an exact result
• A complete dichotomy rises from the capture of vanishing signatures

This page was built for publication: