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)

You are missing something. The easiest way to see this is by considering an example. The smallest 3-regular graph is the complete graph $K_{4}$.

Let $G=(V,E)$ be a graph. Then $G$ has at least $1+|V|$ vertex covers. This bound is tight for complete graphs, so $K_{4}$ has $5$ vertex covers. Convince yourself that ${\text{Holant}}({\text{2-stretch}}(K_{4}),{\text{OR}}_{2},{\text{EQUAL}}_{3})$ has exactly $5$ satisfying assignments. This is a necessary condition for ${\text{Holant}}({\text{2-stretch}}(G),{\text{OR}}_{2},{\text{EQUAL}}_{3})$ to be the number of vertex covers in (a 3-regular graph) $G$.

${\text{Holant}}({\text{2-stretch}}(G),{\text{EQUAL}}_{2},{\text{OR}}_{3})={\text{Holant}}(G,{\text{OR}}_{3})$ is not the problem of counting vertex covers over 3-regular graphs. It is counting edge covers over 3-regular graphs. For any graph, the number of edge covers is at least $1+|E|$. For $K_{4}$, this bound is $7$. Now convince yourself that ${\text{Holant}}(G,{\text{OR}}_{3})$ has at least $7$ (which is more than $5$) satisfying assignments.

Bender2k14 (talk) 13:10, 5 December 2020 (UTC)