论文标题
在稀疏随机图和超图上采样对称吉布斯分布
On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs
论文作者
论文摘要
我们引入了有效的算法，用于从稀疏随机图上的对称吉布斯分布中进行近似采样。我们考虑的示例包括（但不限于）自旋系统和自旋玻璃的重要分布，例如$ q \ geq 2 $的Q状态抗磁磁POTTS模型，包括色彩，包括随机K-CNF配方的不等的溶液中的均匀溶液。最后，我们提出了一种用于从称为K-Spin模型的自旋玻璃分布采样的算法。据我们所知，这是第一个在非琐碎参数范围内运行的自旋胶流的第一个严格分析，有效的算法。 我们的方法建立在[Efthymiou：Soda 2012]中引入的一种方法上。对于对称gibbs分布的随机（超级）图，其参数在一定范围内，我们的算法具有以下属性：在输入实例上，概率$ 1-o（1）$，它在$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ N^{ - ω（1）} $ n^$ n^{ - ω（1）} $ n use的配置中产生了一个配置。时间复杂度为$ o（（n \ log n）^2）$。 该算法需要一系列参数，对于图形案例，这些参数与树木独立性区域一致，参数w.r.t.预期度d。对于唯一性不太限制的超图案例，我们超越了唯一性。我们的方法以新颖的方式利用了吉布斯分布与所谓的教师模型之间的连续性概念。
We introduce efficient algorithms for approximate sampling from symmetric Gibbs distributions on the sparse random (hyper)graph. The examples we consider include (but are not restricted to) important distributions on spin systems and spin-glasses such as the q state antiferromagnetic Potts model for $q\geq 2$, including the colourings, the uniform distributions over the Not-All-Equal solutions of random k-CNF formulas. Finally, we present an algorithm for sampling from the spin-glass distribution called the k-spin model. To our knowledge this is the first, rigorously analysed, efficient algorithm for spin-glasses which operates in a non trivial range of the parameters. Our approach builds on the one that was introduced in [Efthymiou: SODA 2012]. For a symmetric Gibbs distribution $μ$ on a random (hyper)graph whose parameters are within an certain range, our algorithm has the following properties: with probability $1-o(1)$ over the input instances, it generates a configuration which is distributed within total variation distance $n^{-Ω(1)}$ from $μ$. The time complexity is $O((n\log n)^2)$. The algorithm requires a range of the parameters which, for the graph case, coincide with the tree-uniqueness region, parametrised w.r.t. the expected degree d. For the hypergraph case, where uniqueness is less restrictive, we go beyond uniqueness. Our approach utilises in a novel way the notion of contiguity between Gibbs distributions and the so-called teacher-student model.
