ECCC-Report TR07-003https://eccc.weizmann.ac.il/report/2007/003Comments and Revisions published for TR07-003en-usMon, 08 Jan 2007 17:58:47 +0200
Paper TR07-003
| Bases Collapse in Holographic Algorithms |
Jin-Yi Cai,
Pinyan Lu
https://eccc.weizmann.ac.il/report/2007/003Holographic 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 problem without modulo 7 is $\#$P-complete,and counting mod 2 is NP-hard.
We give a general collapse theorem for bases of dimension 4 to dimension 2 in the holographic algorithms framework. We also define an extension of holographic algorithms to allow more general support vectors. Finally we give a bases folding theorem showing that in a natural setting the support vectors can be simulated by basis of dimension 2.
Mon, 08 Jan 2007 17:58:47 +0200https://eccc.weizmann.ac.il/report/2007/003