Holographic algorithms on domains of general size

DOI10.1007/s00224-022-10088-7MaRDI QIDQ6109063

Zhiguo Fu, Jin-Yi Cai

Publication date: 26 July 2023

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

zbMATH Keywords

holographic algorithmsmatchgatessimultaneous realizability problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• Holographic algorithms: from art to science
• On the theory of matchgate computations
• Basis collapse in holographic algorithms
• On symmetric signatures in holographic algorithms
• Holographic algorithms: the power of dimensionality resolved
• Some observations on holographic algorithms
• On blockwise symmetric matchgate signatures and higher domain \#CSP
• The complexity of planar Boolean \#CSP with complex weights
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• Valiant's holant theorem and matchgate tensors
• Computational complexity of counting problems on 3-regular planar graphs
• Holographic Algorithms on Domain Size k > 2
• The statistics of dimers on a lattice
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Holographic Algorithms
• Some Results on Matchgates and Holographic Algorithms
• Complexity Dichotomies for Counting Problems
• Dimer problem in statistical mechanics-an exact result
• Basis collapse for holographic algorithms over all domain sizes
• Base collapse of holographic algorithms
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP