Holographic Approximation: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
 
Line 1: Line 1:
=Holant Problem =
=Holant Problem =


<math>f(a,u,d,x):=a*((u+1)(1+x)^d+(u-1)(1-x)^d)/((u+1)(1+x)^d-(u-1)(1-x)^d)</math>
<math>f(a,u,d,x):=a*((u+1)(1+x)^d+(u-1)(1-x)^d)/((u+1)(1+x)^d-(u-1)(1-x)^d)\,</math>


== Recursion on tree ==
== Recursion on tree ==

Latest revision as of 02:18, 6 May 2012

Holant Problem

[math]\displaystyle{ f(a,u,d,x):=a*((u+1)(1+x)^d+(u-1)(1-x)^d)/((u+1)(1+x)^d-(u-1)(1-x)^d)\, }[/math]

Recursion on tree

[math]\displaystyle{ Z_b(G,e)=\#\{\sigma_G\mid \sigma_G(e)=b\}=\sum_{\sigma\in[q]^G\atop\sigma(e)=b}wt(\sigma) }[/math]

[math]\displaystyle{ \begin{align} Z_0(T,e) &= \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_\ell \prod_{i\in S}Z_{1}(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i)\\ Z_1(T,e) &= \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_{\ell+1} \prod_{i\in S}Z_1(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i) \end{align} }[/math]

[math]\displaystyle{ \begin{align} R_T &= \frac{Z_0(T,e)}{Z_1(T,e)}\\ &= \left( \sum_{\ell=0}^k \sum_{S\in{[k]\choose \ell}} f_\ell\prod_{i\in S}Z_{1}(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i) \right) \Bigg / \left( \sum_{\ell=0}^k \sum_{S\in{[k]\choose \ell}} f_{\ell+1}\prod_{i\in S}Z_1(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i) \right) \end{align} }[/math]