Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Vinay Choudhary:

TR06-048 | 9th April 2006
Jin-Yi Cai, Vinay Choudhary

Some Results on Matchgates and Holographic Algorithms

We establish a 1-1 correspondence between Valiant's
character theory of matchgate/matchcircuit
and his signature theory of planar-matchgate/matchgrid,
thus unifying the two theories in expressibility.
Previously we had established a complete characterization
of general matchgates, in terms of a set of
useful Grassmann-Pl{\"u}cker identities.
With this correspondence,
we give a corresponding ... more >>>

TR06-018 | 8th February 2006
Jin-Yi Cai, Vinay Choudhary

On the Theory of Matchgate Computations

Valiant has proposed a new theory of algorithmic
computation based on perfect matchings and the Pfaffian.
We study the properties of {\it matchgates}---the basic
building blocks in this new theory. We give a set of
algebraic identities
which completely characterize these objects in terms of
the ... more >>>

TR05-118 | 16th October 2005
Jin-Yi Cai, Vinay Choudhary

Valiant's Holant Theorem and Matchgate Tensors

We propose matchgate tensors as a natural and proper language
to develop Valiant's new theory of Holographic Algorithms.
We give a treatment of the central theorem in this theory---the Holant
Theorem---in terms of matchgate tensors.
Some generalizations are presented.

more >>>

ISSN 1433-8092 | Imprint