Holographic Algorithm - History

History

As with any type of reduction, a holographic reduction does not, by itself, yield a polynomial time algorithm. In order to get a polynomial time algorithm, the problem being reduced to must also have a polynomial time algorithm. Valiant's original application of holographic algorithms used a holographic reduction to a problem where every constraint is realizable by matchgates, which he had just proved is tractable by a further reduction to counting the number of perfect matchings in a planar graph. The latter problem is tractable by the FKT algorithm, which dates to the 1960s.

Soon after, Valiant found holographic algorithms with reductions to matchgates for #₇Pl-Rtw-Mon-3CNF and #₇Pl-3/2Bip-VC. These problems may appear somewhat contrived, especially with respect to the modulus. Both problems were already known to be #P-hard when ignoring the modulus and Valiant supplied proofs of #P-hardness modulo 2, which also used holographic reductions. Valiant found these two problems by a computer search that looked for problems with holographic reductions to matchgates. He called their algorithms accidental algorithms, saying "when applying the term accidental to an algorithm we intend to point out that the algorithm arises from satisfying an apparently onerous set of constraints." The "onerous" set of constraints in question are polynomial equations that, if satisfied, imply the existence of a holographic reduction to matchgate realizable constraints.

After several years of developing (what is known as) matchgate signature theory, Jin-Yi Cai and Pinyan Lu were able to explain the existence of Valiant's two accidental algorithms. These two problem are just special cases of two much larger families of problems: #_2k-1Pl-Rtw-Mon-kCNF and #_2k-1Pl-k/2Bip-VC for any positive integer k. The modulus 7 is just the third Mersenne number and Cai and Lu showed that these types of problems with the parameter k have holographic reductions to matchgates exactly when the modulus is the kth Mersenne number.

Around the same time, Jin-Yi Cai, Pinyan Lu and Mingji Xia gave the first holographic algorithm that did not reduce to a problem that is tractable by matchgates. Instead, they reduced to a problem that is tractable by Fibonacci gates, which are symmetric constraints who's truth tables satisfy a recurrence relation similar to one that defines the Fibonacci numbers. They also used holographic reductions to prove that certain counting problems are #P-hard. Since then, holographic reductions have been used extensively as ingredients in both polynomial time algorithms and proofs of #P-hardness.