Harnessing the Bethe free energy.
Harnessing the Bethe free energy.
复制标题
利用伯特自由能。
DOI：
10.1002/rsa.20692
复制
发表时间：
2016-12
影响因子：
1
通讯作者：
Coja-Oghlan, Amin
中科院分区：
文献类型：
--
作者：
Bapst, Victor;Coja-Oghlan, Amin
组合学、计算机科学和物理学中的一大类问题可以沿着下面的路线来描述。在有限域上有大量的变量，它们通过约束相互作用，每个约束都绑定一些变量，并鼓励或阻止某些值的组合。例子包括k-SAT问题或伊辛模型。这样的模型自然会在分配集上产生吉布斯测度，其特征在于它的配分函数。本文讨论了由稀疏随机（超）图引起的变量和约束之间的相互作用的问题的配分函数。根据物理学预测，如果基础模型具有某些性质，则称为“副本对称腔方法”的通用配方产生配分函数的正确值[Krzkala等人，PNAS（2007）10318-10323]。在这个猜想的指导下，我们证明了腔方法成功的一般充分条件。证明是基于一个“正则引理”的概率措施集的形式为有限Ω和一个大的n可能是独立的利益。© 2016 Wiley Periodicals，Inc.随机结构算法，49，694-741，2016
A wide class of problems in combinatorics, computer science and physics can be described along the following lines. There are a large number of variables ranging over a finite domain that interact through constraints that each bind a few variables and either encourage or discourage certain value combinations. Examples include the k‐SAT problem or the Ising model. Such models naturally induce a Gibbs measure on the set of assignments, which is characterised by its partition function. The present paper deals with the partition function of problems where the interactions between variables and constraints are induced by a sparse random (hyper)graph. According to physics predictions, a generic recipe called the “replica symmetric cavity method” yields the correct value of the partition function if the underlying model enjoys certain properties [Krzkala et al., PNAS (2007) 10318–10323]. Guided by this conjecture, we prove general sufficient conditions for the success of the cavity method. The proofs are based on a “regularity lemma” for probability measures on sets of the form for a finite Ω and a large n that may be of independent interest. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 694–741, 2016
登录
查看更多内容
影响因子：
2.4
作者：
Bapst, Victor;Coja-Oghlan, Amin;Vilenchik, Dan
通讯作者：
Vilenchik, Dan
影响因子：
1.8
作者：
Dembo, Amir;Montanari, Andrea
通讯作者：
Montanari, Andrea
影响因子：
2.3
作者：
Bayati, Mohsen;Gamarnik, David;Tetali, Prasad
通讯作者：
Tetali, Prasad
影响因子：
1.6
作者：
ALDOUS, DJ
通讯作者：
ALDOUS, DJ
DOI：
10.1090/s0894-0347-04-00464-3
发表时间：
2004-01-01
影响因子：
3.9
作者：
Achlioptas, D;Peres, Y
通讯作者：
Peres, Y