ECCC-Report TR06-135https://eccc.weizmann.ac.il/report/2006/135Comments and Revisions published for TR06-135en-usSun, 22 Oct 2006 14:11:50 +0200
Paper TR06-135
| On Symmetric Signatures in Holographic Algorithms |
Jin-Yi Cai,
Pinyan Lu
https://eccc.weizmann.ac.il/report/2006/135The 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.
Sun, 22 Oct 2006 14:11:50 +0200https://eccc.weizmann.ac.il/report/2006/135