Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-020 | 11th March 2007 00:00

Holographic Algorithms: The Power of Dimensionality Resolved

RSS-Feed




TR07-020
Authors: Jin-Yi Cai, Pinyan Lu
Publication: 11th March 2007 19:50
Downloads: 2973
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint