2013/05/07 by Jin‐Yi Cai, Cai, Jin-Yi, Zhiguo Fu +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1305.1409
openalex publication_date 2013/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Holographic algorithms with matchgates are a novel approach to design polynomial time computation. It uses Kasteleyn's algorithm for perfect matchings, and more importantly a holographic reduction . The two fundamental parameters of a holographic reduction are the domain size k of the underlying problem, and the basis size ℓ. A holographic reduction transforms the computation to matchgates by a linear transformation that maps to (a tensor product space of) a linear space of dimension 2ℓ. We prove a sharp basis collapse theorem, that shows that for domain size 3 and 4, all non-trivial holographic reductions have basis size ℓ collapse to 1 and 2 respectively. The main proof techniques are Matchgates Identities, and a Group Property of matchgates signatures.