论文标题
双方扩展器上通用自旋系统的快速算法
Fast algorithms for general spin systems on bipartite expanders
论文作者
论文摘要
旋转系统是一个框架，其中将图的顶点从有限的集合中分配给旋转。相邻旋转之间的相互作用会产生重量，因此自旋分配也可以看作是加权图同态。近似分区函数（自旋分配的骨料重量）或从结果概率分布中进行采样的问题通常对于一般图表很棘手。 在这项工作中，我们考虑了两分股东$δ$定型图上的任意旋转系统，包括两分的随机$δ$ remargular图。每当图形的程度和光谱间隙足够大时，我们就会为通用自旋系统的快速近似采样和计数算法。我们的方法概括了Jenseen等人的技术。和Chen等。通过表明两分扩展器上的典型配置对应于自旋系统的“双晶体”；然后，使用合适的聚合物模型，我们展示了如何在$ \ tilde {o}（n^2）$ time中进行采样并近似分区功能，其中$ n $是图形的大小。
A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assignment can also be viewed as a weighted graph homomorphism. The problem of approximating the partition function (the aggregate weight of spin assignments) or of sampling from the resulting probability distribution is typically intractable for general graphs. In this work, we consider arbitrary spin systems on bipartite expander $Δ$-regular graphs, including the canonical class of bipartite random $Δ$-regular graphs. We develop fast approximate sampling and counting algorithms for general spin systems whenever the degree and the spectral gap of the graph are sufficiently large. Our approach generalises the techniques of Jenseen et al. and Chen et al. by showing that typical configurations on bipartite expanders correspond to "bicliques" of the spin system; then, using suitable polymer models, we show how to sample such configurations and approximate the partition function in $\tilde{O}(n^2)$ time, where $n$ is the size of the graph.
