该研究探讨了对于在 d - 正则图上,存在非唯一性的两个自旋系统(包括独立集模型和反铁磁伊辛模型),在逼近其配分函数或者用该模型逼近抽样是 NP 难的。同时,该研究提出了一种新的方法,用二分图本地树状图结构来描述两自旋系统,并标志着通过随机化降低最大割问题的计算复杂性的新里程碑。
Mar, 2012
研究了在随机图上估计硬核模型和反铁磁伊辛模型的区别,证明了对于反铁磁伊辛模型在非一意性区域内不存在近似方案。
本文扩展 Weitz 的方法,针对最大度数为 d 的图上的反铁磁 Ising 模型的分区函数,推导出一个确定性完全多项式逼近方法,主要结果是证明了在 d - 正则树上,两态反铁磁自旋系统的弱空间混合意味着强空间混合。
Jul, 2011
本文通过采用空腔方法,研究硬核模型在随机规则图上的最密堆积密度与相变性质,证明了硬核模型是结构玻璃和堵塞问题最简单的平均场晶格模型。
Jun, 2013
本文研究了在具有一致稀疏图序列的随机树 T 上的同质化因子模型的自由能密度存在性,并通过新的插值方案证明了存在性并具体计算了该量。通过实例计算,我们证明了该极限与在 T 上的 Belief Propagation(Bethe)递归的适当不动点处的 Bethe 自由能函数重合。
Oct, 2011
论文提出了信息论阈值的上下界,并进一步证明了当组数较大且特定参数取值时,物理条件下的凝聚阈值是具有严格界限的,若邻居间与组间边缘概率不同,则分配问题可以解决,否则无算法可优于随机。
Jan, 2016
研究随机 CSP 问题和多项式时间算法无法寻找解决方案的相位转变,并运用一般技术准确地证明 $k$- 着色的相位转变推出所有已知多项式时间算法的失败点。
Mar, 2008
在统计学中称为 “块模型”,在理论计算机科学中称为 “种植分区模型” 的随机图模型被研究,研究者在此基础上提出了一个关于稀疏种植分区模型的算法阈值的精确预测,并提供了一种与真实分区相关的高效聚类算法,完善了该猜想的证明。
Nov, 2013
本文利用随机变量的最大统计量将分区函数与之相关联,提供了一种新的框架,通过随机扰动模型上的 MAP 推断来近似和限制分区函数,从而可以使用图割等高效 MAP 求解器来评估相应的分区函数,证明我们的方法在典型的 “高信号 - 高耦合” 区域中表现出色,这导致了难以处理的凹凸不平的能量景观。
Jun, 2012
本文研究了具有 $q$ 种颜色的 Potts 模型在带权图序列上的性质,证明了一定条件下的平均场预测在渐近意义下的正确性,应用于 Ising 和 Potts 模型,进一步证明了在渐近正则图上铁磁 Potts 模型和 Ising 模型的极限对数处理函数的普适性,并为渐近正则图上的 Potts 模型推导了大偏差原理。
Aug, 2015