Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Pinyan Lu:

TR11-093 | 8th June 2011
Pinyan Lu

Complexity Dichotomies of Counting Problems

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

TR07-020 | 11th March 2007
Jin-Yi Cai, Pinyan Lu

Holographic Algorithms: The Power of Dimensionality Resolved

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
We completely resolve the problem of the power of higher dimensional
bases. We prove that 2-dimensional bases are universal for
holographic ... more >>>

TR07-019 | 10th March 2007
Jin-Yi Cai, Pinyan Lu

On Block-wise Symmetric Signatures for Matchgates

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

more >>>

TR07-003 | 5th January 2007
Jin-Yi Cai, Pinyan Lu

Bases Collapse in Holographic Algorithms

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

TR06-145 | 1st December 2006
Jin-Yi Cai, Pinyan Lu

Holographic Algorithms: From Art to Science

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

TR06-135 | 22nd October 2006
Jin-Yi Cai, Pinyan Lu

On Symmetric Signatures in Holographic Algorithms

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

ISSN 1433-8092 | Imprint