Talk:Holographic algorithm

"^ a b c d Holographic Algorithms: From Art to Science, by Jin-Yi Cai and Pinyan Lu, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007" this link is broken —Preceding unsigned comment added by 212.76.37.154 (talk) 16:41, 6 September 2009 (UTC)

It works now. Bender2k14 (talk) 05:08, 14 October 2009 (UTC)

Expert

BTW, I am an expert in holographic algorithms. Eventually I will reorder, elaborate existing, and add content. If anyone has questions that they would like the article to answer, please ask them here. I am also interested in suggestions for ordering and grouping content. Bender2k14 (talk) 18:28, 1 September 2010 (UTC)

I am working on a draft that will have major changes/additions. Bender2k14 (talk) 18:15, 1 May 2011 (UTC)

Problem with specific example

Bender2k14 -

For vertex cover: if you're starting with a 3-regular graph (really, any graph) and doing a 2-stretch on it, then by virtue of the graph transformation you just did, the $f_{u}$ constraint to your Holant definition should be $\mathrm {EQUAL_{2}}$, no? $OR_{2}$ doesn't really make sense, since the introduction of $U$ is just splitting edges (and both new resultant edges will be the same variable).

I think you probably want to switch the last two arguments, so that it reads $\mathrm {Holant} (H,\mathrm {EQUAL_{2}} ,\mathrm {OR_{3}} )$ - $OR_{3}$ makes much more sense as a $V$ constraint, since you're just looking for "at least one incident edge" (out of the three implied by the definition of 3-regular)

Regrettably, this messes up the math as well. What you should have is:

${\begin{aligned}f_{u}&=&\mathrm {EQUAL_{2}} &=&{\begin{bmatrix}1&0&0&1\end{bmatrix}}\\f_{v}&=&\mathrm {OR_{3}} &=&{\begin{bmatrix}0&1&1&1&1&1&1&1\end{bmatrix}}^{T}\end{aligned}}$

Once we have these correct vector logic constructs, we can actually carry out the reduction:

${\begin{array}{rccc}f_{u}^{\otimes |U|}f_{v}^{\otimes |V|}&=&\mathrm {EQUAL_{2}} ^{\otimes |U|}&\mathrm {OR_{3}} ^{\otimes |V|}\\f_{u}^{\otimes |U|}T^{\otimes |E|}(T^{-1})^{\otimes |E|}f_{v}^{\otimes |V|}&=&{\begin{bmatrix}1&0&0&1\end{bmatrix}}^{\otimes |U|}{\begin{bmatrix}0&1\\1&0\end{bmatrix}}^{\otimes |E|}&{\begin{bmatrix}0&1\\1&0\end{bmatrix}}^{\otimes |E|}{\begin{bmatrix}0\\1\\1\\1\\1\\1\\1\\1\end{bmatrix}}^{\otimes |V|}\\{\Bigl (}f_{u}T^{\otimes \deg(u)}{\Bigr )}^{\otimes |U|}{\Bigl (}f_{v}(T^{-1})^{\otimes \deg(v)}{\Bigr )}^{\otimes |V|}&=&\left({\begin{bmatrix}1&0&0&1\end{bmatrix}}{\begin{bmatrix}0&0&0&1\\0&0&1&0\\0&1&0&0\\1&0&0&0\\\end{bmatrix}}\right)^{\otimes |U|}&\left({\begin{bmatrix}0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&0\\0&0&0&0&1&0&0&0\\0&0&0&1&0&0&0&0\\0&0&1&0&0&0&0&0\\0&1&0&0&0&0&0&0\\1&0&0&0&0&0&0&0\end{bmatrix}}{\begin{bmatrix}0\\1\\1\\1\\1\\1\\1\\1\end{bmatrix}}\right)^{\otimes |V|}\\[3em]&=&\left({\begin{bmatrix}1&0&0&1\end{bmatrix}}\right)^{\otimes |U|}&\left({\begin{bmatrix}1\\1\\1\\1\\1\\1\\1\\0\end{bmatrix}}\right)^{\otimes |V|}\\[4em]&=&\mathrm {EQUAL_{2}} ^{\otimes |U|}&\mathrm {NAND_{3}} ^{\otimes |V|}\end{array}}$

Let me know if this makes sense / if I'm missing anything. Thanks!

Datamance (talk) 02:20, 5 December 2020 (UTC)