Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-135 | 22nd October 2006 00:00

On Symmetric Signatures in Holographic Algorithms


Authors: Jin-Yi Cai, Pinyan Lu
Publication: 22nd October 2006 14:11
Downloads: 1205


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 =$ NP, we must begin to develop a theory which captures the limit of expressibility and power of this new methodology.

In holographic algorithms, {\it 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~\cite{CC-icalp} where only symmetric signatures over the Hadamard basis (special basis of size 1) were obtained. This in particular confirms a conjecture by Valiant. We also give a complete characterization of Boolean symmetric signatures over bases of size 1.

ISSN 1433-8092 | Imprint