Journal
LINEAR ALGEBRA AND ITS APPLICATIONS
Volume 438, Issue 2, Pages 690-707Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.laa.2011.02.032
Keywords
Fibonacci gates; Holographic algorithm; Counting problems; Dichotomy theorem; Signature theory; Matchgates
Categories
Funding
- NSF [CCF-0830488, CCF-0511679]
Ask authors/readers for more resources
We introduce Fibonacci gates as a polynomial time computable primitive, and develop a theory of holographic algorithms based on these gates. The Fibonacci gates play the role of matchgates in Valiant's theory (Valiant (2008)[19]). They give rise to polynomial time computable counting problems on general graphs, while matchgates mainly work over planar graphs only. We develop a signature theory and characterize all realizable signatures for Fibonacci gates. For bases of arbitrary dimensions we prove a basis collapse theorem. We apply this theory to give new polynomial time algorithms for certain counting problems. We also use this framework to prove that some slight variations of these counting problems are #P-hard. Holographic algorithms with Fibonacci gates prove to be useful as a general tool for classification results of counting problems (dichotomy theorems (Cai et al. (2009)[7])). (C) 2011 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available