论文标题
小型扩展器上POTTS模型的有效算法
Efficient algorithms for the Potts model on small-set expanders
论文作者
论文摘要
近似计数的新兴趋势是表明尽管结果最差，但在典型情况下，某些“低温”问题在典型的情况下很容易。对于常规图的类别，通常表明可以通过算法利用扩展，并且由于随机常规图是具有很高概率的良好扩展器，因此问题通常是可以处理的。受到独特游戏的次指定时间算法使用的方法的启发，我们开发了一种近似算法，用于在具有小型扩展条件的图形上为铁磁Potts模型的分区函数。在这样的图中，探索模型接近地面状态的状态空间可能不足以实现，我们方法的新功能是有效地找到一组较大的“伪地面状态”，因此足以探索每个伪地面周围的模型。
An emerging trend in approximate counting is to show that certain `low-temperature' problems are easy on typical instances, despite worst-case hardness results. For the class of regular graphs one usually shows that expansion can be exploited algorithmically, and since random regular graphs are good expanders with high probability the problem is typically tractable. Inspired by approaches used in subexponential-time algorithms for Unique Games, we develop an approximation algorithm for the partition function of the ferromagnetic Potts model on graphs with a small-set expansion condition. In such graphs it may not suffice to explore the state space of the model close to ground states, and a novel feature of our method is to efficiently find a larger set of `pseudo-ground states' such that it is enough to explore the model around each pseudo-ground state.
