Holographic Algorithms Beyond Matchgates

Jin-Yi Cai, Heng Guo, Tyson Williams

Research output: Contribution to journalArticlepeer-review


Holographic algorithms introduced by Valiant have two ingredients: matchgates, which are gadgets realizing local constraint functions by weighted planar perfect matchings, and holographic reductions, which show equivalences among problems with different descriptions via basis transformations. In this paper, we replace matchgates in the paradigm above by the affine type and the product type constraint functions, which are known to be tractable in general (not necessarily planar) graphs. We present polynomial-time algorithms to decide if a given counting problem has a holographic reduction to another problem defined by the affine or product-type functions. We also give polynomial-time algorithms to the same problems for symmetric functions, where the complexity is measured in terms of the (exponentially more) succinct representations. The latter result implies that the symmetric Boolean Holant dichotomy (Cai, Guo, and Williams, SICOMP 2016) is efficiently decidable. Our proof techniques are mainly algebraic.
Original languageEnglish
Pages (from-to)102-129
Number of pages28
JournalInformation and Computation
Early online date8 Jan 2018
Publication statusPublished - 1 Apr 2018


Dive into the research topics of 'Holographic Algorithms Beyond Matchgates'. Together they form a unique fingerprint.

Cite this