Abstract
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 polynomialtime algorithms to decide if a given counting problem has a holographic reduction to another problem defined by the affine or producttype functions. We also give polynomialtime 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 language  English 

Pages (fromto)  102129 
Number of pages  28 
Journal  Information and Computation 
Volume  259 
Early online date  8 Jan 2018 
DOIs  
Publication status  Published  1 Apr 2018 
Fingerprint
Dive into the research topics of 'Holographic Algorithms Beyond Matchgates'. Together they form a unique fingerprint.Profiles

Heng Guo
 School of Informatics  Reader in Algorithms and Complexity
 Laboratory for Foundations of Computer Science  Lecturer in Algorithms and Complexity
 Foundations of Computation
Person: Academic: Research Active (Teaching)