Some Results on Matchgates and Holographic Algorithms

DOI10.1007/11786986_61zbMath1223.68120OpenAlexW105846551MaRDI QIDQ3613802

Publication date: 12 March 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11786986_61

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) General topics in the theory of algorithms (68W01)

Related Items (18)

Some observations on holographic algorithms ⋮ Erratum to: ``Signature theory in holographic algorithms ⋮ On the theory of matchgate computations ⋮ On blockwise symmetric signatures for matchgates ⋮ Valiant's holant theorem and matchgate tensors ⋮ Computational complexity of counting problems on 3-regular planar graphs ⋮ \(P\) versus \(NP\) and geometry ⋮ Holographic algorithms by Fibonacci gates ⋮ Holographic algorithms without matchgates ⋮ Holographic algorithms on domains of general size ⋮ Holographic reduction for some counting problems ⋮ Signature theory in holographic algorithms ⋮ Holographic algorithms on bases of rank 2 ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ On symmetric signatures in holographic algorithms ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Holographic algorithms: the power of dimensionality resolved ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints

This page was built for publication: Some Results on Matchgates and Holographic Algorithms