All reports by Author Pinyan Lu:

__
TR11-093
| 8th June 2011
__

Pinyan Lu#### Complexity Dichotomies of Counting Problems

__
TR07-020
| 11th March 2007
__

Jin-Yi Cai, Pinyan Lu#### Holographic Algorithms: The Power of Dimensionality Resolved

__
TR07-019
| 10th March 2007
__

Jin-Yi Cai, Pinyan Lu#### On Block-wise Symmetric Signatures for Matchgates

__
TR07-003
| 5th January 2007
__

Jin-Yi Cai, Pinyan Lu#### Bases Collapse in Holographic Algorithms

__
TR06-145
| 1st December 2006
__

Jin-Yi Cai, Pinyan Lu#### Holographic Algorithms: From Art to Science

__
TR06-135
| 22nd October 2006
__

Jin-Yi Cai, Pinyan Lu#### On Symmetric Signatures in Holographic Algorithms

Pinyan Lu

In order to study the complexity of counting problems, several interesting frameworks have been proposed, such as Constraint Satisfaction Problems (#CSP) and Graph Homomorphisms. Recently, we proposed and explored a novel alternative framework, called Holant Problems. It is a refinement with a more explicit role for constraint functions. Both graph ... more >>>

Jin-Yi Cai, Pinyan Lu

Valiant's theory of holographic algorithms is a novel methodology

to achieve exponential speed-ups in computation. A fundamental

parameter in holographic algorithms is the dimension of the linear basis

vectors.

We completely resolve the problem of the power of higher dimensional

bases. We prove that 2-dimensional bases are universal for

holographic ...
more >>>

Jin-Yi Cai, Pinyan Lu

We give a classification of block-wise symmetric signatures

in the theory of matchgate computations. The main proof technique

is matchgate identities, a.k.a. useful Grassmann-Pl\"{u}cker

identities.

Jin-Yi Cai, Pinyan Lu

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This ... more >>>

Jin-Yi Cai, Pinyan Lu

We develop the theory of holographic algorithms. We give

characterizations of algebraic varieties of realizable

symmetric generators and recognizers on the basis manifold,

and a polynomial time decision algorithm for the

simultaneous realizability problem.

Using the general machinery we are able to give

unexpected holographic algorithms for

some counting problems, ...
more >>>

Jin-Yi Cai, Pinyan Lu

The most intriguing aspect of the new theory of matchgate computations and holographic algorithms by Valiant~\cite{Valiant:Quantum} \cite{Valiant:Holographic} is that its reach and ultimate capability are wide open. The methodology produces unexpected polynomial time algorithms solving problems which seem to require exponential time. To sustain our belief in P $\not =$ ... more >>>