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)

Ah, how very silly indeed - I mixed up vertex and edge cover! $f_{u}=\mathrm {OR_{2}}$ and $f_{v}=\mathrm {EQUAL_{3}}$ absolutely make intuitive sense, then, as $f_{v}=\mathrm {EQUAL_{3}}$ is just looking for agreement on a particular assignment w.r.t. the halves of the split edges touching any given node, while $f_{u}=\mathrm {OR_{2}}$ has us covered on the "every edge has at least one endpoint in the vertex cover" part. My mistake - thank you for the correction!

For reasons that you just pointed out, this means that the reduction I just did obviously does not satisfy the counting of independent sets (something I would have realized earlier if I had been more careful about checking my work!). This only makes me ever the more curious about the relationship between vertex cover ($\mathrm {EQUAL_{2}} ^{\otimes |U|}\mathrm {OR_{3}} ^{\otimes |V|}$) and the reduction of $\mathrm {EQUAL_{2}} ^{\otimes |U|}\mathrm {NAND_{3}} ^{\otimes |V|}$... what counting problem is embodied by the latter formulation? Or, more informally, what would you call "groups of edges such that no three edges touch the same point?"

Datamance (talk) 22:13, 7 December 2020 (UTC)

Oh, sorry. I just saw this.

The complexity of $\mathrm {EQUAL_{2}} ^{\otimes |U|}\mathrm {NAND_{3}} ^{\otimes |V|}$ (i.e. "groups of edges such that no three edges touch the same point") is the same as $\mathrm {EQUAL_{2}} ^{\otimes |U|}\mathrm {OR_{3}} ^{\otimes |V|}$ (i.e. counting vertex covers) because these problems are "complements". One can reduce each problem to the other by subtracting the number of satisfying assignments from $2^{|U|}$. Alternatively, one can think of $\mathrm {EQUAL_{2}} ^{\otimes |U|}\mathrm {NAND_{3}} ^{\otimes |V|}$ as the problem of counting vertex covers when an assignment of $0$ means the corresponding edge is in the vertex cover (and $1$ means the corresponding edge is not in the vertex cover). Therefore, the problem $\mathrm {EQUAL_{2}} ^{\otimes |U|}\mathrm {NAND_{3}} ^{\otimes |V|}$ is essentially a non-canonical way to express the problem counting vertex covers.

Bender2k14 (talk) 11:57, 19 July 2021 (UTC)