论文标题
在有限度图上近似平均值的复杂性
The complexity of approximating averages on bounded-degree graphs
论文作者
论文摘要
我们证明，除非p = np，否则在某个乘法常数内没有多项式时间算法近似于最大程度6的独立集的平均大小。这是在独立集合中定义的硬核模型的更一般结果的特殊情况，该模型定义为由参数$λ> 0 $加权的独立集合。 In the general setting, we prove that, unless P=NP, for all $Δ\geq 3$, all $λ>λ_c(Δ)$, there is no FPTAS which applies to all graphs of maximum degree $Δ$ for computing the average size of the independent set in the Gibbs distribution, where $λ_c(Δ)$ is the critical point for the uniqueness/non-uniqueness phase transition on the $Δ$-regular 树。此外，我们证明，对于$λ$，在这个非唯一性区域的密集集中，问题是在某个恒定因素之内近似np-hard。我们的工作扩展到抗磁性ISING模型，并将其推广到所有2-Spin抗铁磁模型，从而确定了计算树非独特区域中平均磁化的硬度。 以前，Schulman，Sinclair和Srivastava（2015）表明，准确计算平均磁化是＃p-hard，但概率却不知道。 Sly（2010）和Sly and Sun（2014）的硬度结果近似分区函数并不意味着计算平均值的硬度。我们还原中的新成分是对根树的复杂构造，其根部的边际分布同意，但其衍生物不同意。主要的技术贡献是控制哪些边际分布和衍生物是可以实现的，并使用Cauchy的功能方程来争辩小工具的存在。
We prove that, unless P=NP, there is no polynomial-time algorithm to approximate within some multiplicative constant the average size of an independent set in graphs of maximum degree 6. This is a special case of a more general result for the hard-core model defined on independent sets weighted by a parameter $λ>0$. In the general setting, we prove that, unless P=NP, for all $Δ\geq 3$, all $λ>λ_c(Δ)$, there is no FPTAS which applies to all graphs of maximum degree $Δ$ for computing the average size of the independent set in the Gibbs distribution, where $λ_c(Δ)$ is the critical point for the uniqueness/non-uniqueness phase transition on the $Δ$-regular tree. Moreover, we prove that for $λ$ in a dense set of this non-uniqueness region the problem is NP-hard to approximate within some constant factor. Our work extends to the antiferromagnetic Ising model and generalizes to all 2-spin antiferromagnetic models, establishing hardness of computing the average magnetization in the tree non-uniqueness region. Previously, Schulman, Sinclair and Srivastava (2015) showed that it is #P-hard to compute the average magnetization exactly, but no hardness of approximation results were known. Hardness results of Sly (2010) and Sly and Sun (2014) for approximating the partition function do not imply hardness of computing averages. The new ingredient in our reduction is an intricate construction of pairs of rooted trees whose marginal distributions at the root agree but their derivatives disagree. The main technical contribution is controlling what marginal distributions and derivatives are achievable and using Cauchy's functional equation to argue existence of the gadgets.
