Survey propagation as local equilibrium equations

被引:55
作者
Braunstein, A
Zecchina, R
机构
[1] SISSA, I-34100 Trieste, Italy
[2] Abdus Salaam Int Ctr Theoret Phys, I-34100 Trieste, Italy
来源
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT | 2004年
关键词
cavity and replica method; message-passing algorithms; source and channel coding;
D O I
10.1088/1742-5468/2004/06/P06007
中图分类号
O3 [力学];
学科分类号
08 ; 0801 ;
摘要
It has been shown experimentally that a decimation algorithm based on survey propagation (SP) equations allows one to solve efficiently some combinatorial problems over random graphs. We show that these equations can be derived as sum - product equations for the computation of marginals in an extended space where the variables are allowed to take an additional value - - when they are not forced by the combinatorial constraints. An appropriate 'local equilibrium condition' cost/energy function is introduced and its entropy is shown to coincide with the expected logarithm of the number of clusters of solutions as computed by SP. These results may help to clarify the geometrical notion of clusters assumed by SP for random K-SAT or random graph colouring ( where it is conjectured to be exact) and help to explain which kind of clustering operation or approximation is enforced in general/small sized models in which it is known to be inexact.
引用
收藏
页数:18
相关论文
共 35 条
[1]  
Aldous D, 2004, ENCYL MATH SCI, V110, P1
[2]   The ζ(2) limit in the random assignment problem [J].
Aldous, DJ .
RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (04) :381-418
[3]  
BARTHEL W, CONDMAT0403193
[4]  
BERROU C, 1993, IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS 93 : TECHNICAL PROGRAM, CONFERENCE RECORD, VOLS 1-3, P1064, DOI 10.1109/ICC.1993.397441
[5]   From inherent structures to pure states: Some simple remarks and examples [J].
Biroli, G ;
Monasson, R .
EUROPHYSICS LETTERS, 2000, 50 (02) :155-161
[6]  
BRAUNSTEIN A, 2004, UNPUB CLUSTERING RAN
[7]  
BRAUNSTEIN A, 2002, CONDMAT0212451
[8]  
BRAUNSTEIN A, 2002, CSCC0212002
[9]   On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit [J].
Chung, SY ;
Forney, GD ;
Richardson, TJ ;
Urbanke, R .
IEEE COMMUNICATIONS LETTERS, 2001, 5 (02) :58-60
[10]   Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices [J].
Cocco, S ;
Dubois, O ;
Mandler, J ;
Monasson, R .
PHYSICAL REVIEW LETTERS, 2003, 90 (04) :4-472054