May, 2010

独特性阈值处的计算过渡

TL;DR证明了在 $d$- 正则树上 hardcore 模型的唯一性阈值处计算配分函数在最大度数为 $d$ 的图上变得计算困难。通过随机二分图构造,结合重构问题分析和第二时刻方法,建立了定量的统计物理阶段转变计数难度和取样难度的强耦合关系。