All reports by Author Vinay Choudhary:

__
TR06-048
| 9th April 2006
__

Jin-Yi Cai, Vinay Choudhary#### Some Results on Matchgates and Holographic Algorithms

__
TR06-018
| 8th February 2006
__

Jin-Yi Cai, Vinay Choudhary#### On the Theory of Matchgate Computations

__
TR05-118
| 16th October 2005
__

Jin-Yi Cai, Vinay Choudhary#### Valiant's Holant Theorem and Matchgate Tensors

Jin-Yi Cai, Vinay Choudhary

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 >>>

Jin-Yi Cai, Vinay Choudhary

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 >>>

Jin-Yi Cai, Vinay Choudhary

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.