Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Symposium on Discrete Algorithms

Holographic algorithms with unsymmetric signatures

Jin‐Yi Cai, Pinyan Lu

Published Jan 20, 2008• 9 citations
OpenAlex

Abstract

Holographic algorithms were introduced by Valiant as a new methodology to derive polynomial time algorithms. Here information and computation are represented by exponential sums using the so-called signatures. These signatures express superpositions of perfect matchings, and are used to achieve exponential sized cancellations, and thereby exponential speedups. Most holographic algorithms so far used symmetric signatures. In this paper we use unsymmetric signatures to give some new holographic algorithms. We also prove a characterization theorem for a class of realizable un-symmetric signatures, each of which may be used to design new holographic algorithms.

Related papers

On Symmetric Signatures in Holographic Algorithms

In holographic algorithms, symmetric signatures have been particularly useful. We give a complete characterization of these symmetric signatures over all bases of size 1. These improve previous results by Cai and Choudhary (ICALP 2006, vol. 4051, pp. 703–714, 2006) where only symmetric signatures over the Hadamard basis (special basis of size 1) were obtained. In particular, we give a complete list of Boolean symmetric signatures over bases of size 1. It is an open problem whether signatures over bases of higher dimensions are strictly more powerful. The recent result by Valiant (FOCS 2006, pp. 509–517, 2006) seems to suggest that bases of size 2 might be indeed more powerful than bases of size 1. This result is with regard to a restrictive counting version of #SAT called #Pl-Rtw-Mon-3CNF. It is known that the problem is #P-hard, and its mod 2 version is ⊕P-hard. Yet its mod 7 version is solvable in polynomial time by holographic algorithms. This was ac complished by a suitable symmetric signature over a basis of size 2. We show that the same unexpected holographic algorithm can be realized over a basis of size 1. Furthermore we prove that 7 is the only modulus for which such an "accidental algorithm" exists.

•Feb 6, 2008•22 citations

Holographic algorithms

Jin‐Yi Cai

Leslie Valiant recently proposed a theory of holographic algorithms. These novel algorithms achieve exponential speed-ups for certain computational problems compared to naive algorithms for the same problems. The methodology uses Pfaffians and (planar) perfect matchings as basic computational primitives, and attempts to create exponential cancellations in computation. In this article we survey this new theory of matchgate computations and holographic algorithms.

ACM SIGACT News•Jun 1, 2008•8 citations

Holographic algorithms

J.-Y. Cai

Leslie Valiant recently proposed a theory of holographic algorithms.These novel algorithms achieve exponential speed-ups for certain computational problems compared to naive algorithms for the same problems.The methodology uses Pfaffians and (planar) perfect matchings as basic computational primitives, and attempts to create exponential cancellations in computation.In this article we survey this new theory of matchgate computations and holographic algorithms.

Current Developments in Mathematics•Jan 1, 2005•3 citations

Some Results on Matchgates and Holographic Algorithms.

Jin‐Yi Cai, Vinay Choudhary

We establish a 1-1 correspondence between Valiant's character theory of matchgate/matchcircuit [14] and his signature theory of planar-matchgate/matchgrid [16], thus unifying the two theories in expressibility. In [5], we had established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Pl"ucker identities. With this correspondence, we give a corresponding set of identities which completely characterizes planar-matchgates and their signatures. Applying this characterization we prove some negative results for holographic algorithms. On the positive side, we also give a polynomial time algorithm for a simultaneous node-edge deletion problem, using holographic algorithms. Finally we give characterizations of symmetric signatures realizable in the Hadamard basis.

Electronic colloquium on computational complexity•Jan 1, 2006•1 citation

Holographic Algorithms Beyond Matchgates

Jin‐Yi Cai, Heng Guo, Tyson Williams

Holographic algorithms introduced by Valiant are composed of 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 certain 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. More specifically, 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. Our algorithms also find a holographic transformation when one exists. We further present polynomial-time algorithms of the same decision and search problems for symmetric functions, where the complexity is measured in terms of the (exponentially more) succinct representations. The algorithm for the symmetric case also shows that the recent dichotomy theorem for Holant problems with symmetric constraints is efficiently decidable. Our proof techniques are mainly algebraic, e.g., using stabilizers and orbits of group actions.

arXiv:1307.7430•Jul 29, 2013•0 citations

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

Annual Symposium on Foundations of Computer Science•Oct 1, 2010•50 citations
Holographic algorithms were introduced by Valiant as a new methodology to derive polynomial time algorithms. Here information and computation are represented by exponential sums using the so-called signatures. These signatures express superpositions of perfect matchings, and are used to achieve exponential sized cancellations, and thereby exponential speedups. Most holographic algorithms so far used symmetric signatures. In this paper we use unsymmetric signatures to give some new holographic algorithms. We also prove a characterization theorem for a class of realizable un-symmetric signatures, each of which may be used to design new holographic algorithms.
In holographic algorithms, symmetric signatures have been particularly useful. We give a complete characterization of these symmetric signatures over all bases of size 1. These improve previous results by Cai and Choudhary (ICALP 2006, vol. 4051, pp. 703–714, 2006) where only symmetric signatures over the Hadamard basis (special basis of size 1) were obtained. In particular, we give a complete list of Boolean symmetric signatures over bases of size 1. It is an open problem whether signatures over bases of higher dimensions are strictly more powerful. The recent result by Valiant (FOCS 2006, pp. 509–517, 2006) seems to suggest that bases of size 2 might be indeed more powerful than bases of size 1. This result is with regard to a restrictive counting version of #SAT called #Pl-Rtw-Mon-3CNF. It is known that the problem is #P-hard, and its mod 2 version is ⊕P-hard. Yet its mod 7 version is solvable in polynomial time by holographic algorithms. This was ac complished by a suitable symmetric signature over a basis of size 2. We show that the same unexpected holographic algorithm can be realized over a basis of size 1. Furthermore we prove that 7 is the only modulus for which such an "accidental algorithm" exists.
We establish a 1-1 correspondence between Valiant's character theory of matchgate/matchcircuit [14] and his signature theory of planar-matchgate/matchgrid [16], thus unifying the two theories in expressibility. In [5], we had established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Pl"ucker identities. With this correspondence, we give a corresponding set of identities which completely characterizes planar-matchgates and their signatures. Applying this characterization we prove some negative results for holographic algorithms. On the positive side, we also give a polynomial time algorithm for a simultaneous node-edge deletion problem, using holographic algorithms. Finally we give characterizations of symmetric signatures realizable in the Hadamard basis.
Holographic algorithms introduced by Valiant are composed of 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 certain 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. More specifically, 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. Our algorithms also find a holographic transformation when one exists. We further present polynomial-time algorithms of the same decision and search problems for symmetric functions, where the complexity is measured in terms of the (exponentially more) succinct representations. The algorithm for the symmetric case also shows that the recent dichotomy theorem for Holant problems with symmetric constraints is efficiently decidable. Our proof techniques are mainly algebraic, e.g., using stabilizers and orbits of group actions.
Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.