Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-145 | 1st December 2006 00:00

Holographic Algorithms: From Art to Science

RSS-Feed




TR06-145
Authors: Jin-Yi Cai, Pinyan Lu
Publication: 1st December 2006 10:56
Downloads: 5789
Keywords: 


Abstract:

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, modulo certain Mersenne type
integers. These counting problems are #P-complete
without the moduli. Going beyond symmetric signatures,
we define $d$-admissibility and d-realizability
for general signatures, and give a characterization
of 2-admissibility and some general constructions of
admissible and realizable families.



ISSN 1433-8092 | Imprint