Some Results on Matchgates and Holographic Algorithms

DOI10.1007/11786986_61zbMATH Open1223.68120OpenAlexW105846551MaRDI QIDQ3613802FDOQ3613802

Authors: Jin-Yi Cai, Vinay Choudhary 

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

Recommendations

• Holographic algorithms without matchgates
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• On the theory of matchgate computations
• Some observations on holographic algorithms
• Some observations on holographic algorithms
• Holographic algorithms on domains of general size
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP

Mathematics Subject Classification ID

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

Cited In (22)

• Holographic algorithms on bases of rank 2
• Signature Theory in Holographic Algorithms
• On Symmetric Signatures in Holographic Algorithms
• A theory for Valiant's matchcircuits (Extended abstract)
• On blockwise symmetric signatures for matchgates
• Erratum to: ``Signature theory in holographic algorithms
• Signature theory in holographic algorithms
• On the theory of matchgate computations
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Holographic algorithms by Fibonacci gates
• Holographic algorithms on domains of general size
• \(P\) versus \(NP\) and geometry
• Some observations on holographic algorithms
• On symmetric signatures in holographic algorithms
• Holographic algorithms: the power of dimensionality resolved
• Holographic reduction for some counting problems
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• Theory and Applications of Models of Computation
• Holographic algorithms without matchgates
• Matchgates revisited
• Computational complexity of counting problems on 3-regular planar graphs
• Valiant's holant theorem and matchgate tensors

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613802)