全息算法是计数复杂性领域中十分重要的技术，全息算法通过基变换将许多难以处理的计数问题转换成可以高效求解的平面图完美匹配计数问题，推动了后续计数CSP和Holant问题的发展。该文章分析了全息算法的基本理论、原理和使用方法,旨在简化对全息算法的理解并加以应用;给出了几个实例(如平面3-CNF公式的计数问题),以帮助读者理解全息算法中的一些基本原理和方法。相关的原理和方法对解决某些组合计数问题有所帮助。

配分函数的计算属于计数问题类#P，该文章讨论正则图上的对称双态自旋系统的配分函数计算复杂性. 利用计数指数时间假设 (#ETH) 和随机指数时间假设 (rETH), 将该问题类的经典二分定理, 细化到指数型二分定理, 又称细密度二分定理. 换而言之, 证明满足给定易解条件时, 该问题可在多项式时间内求解; 否则, #ETH 成立时, 该问题没有亚指数时间算法. 还针对平面图限制下已有插值方法在构造根号亚指数时间归约时失效的问题, 提出两种解决方案, 并利用这两种方案探讨平面限制下该问题相关的细密度复杂性和二分定理。

大多数计数问题是#P难的，采样是在精确计数困难时进行近似计数的重要方法。该报告将系统介绍报告人近年来在计算采样理论、以及现代蒙特卡罗算法的设计与分析等方面取得的系统性的重要进展，包括：概率图模型和约束满足解的采样的“计算相变”；马尔可夫链蒙特卡罗（MCMC）采样的并行化；采样的局部化算法的新范式。

采样是一类基本的计算问题，从一个解空间中依特定概率分布进行随机采样，这一问题在近似计数、概率推断、统计学习等方面都有着诸多重要的应用。在大数据时代,采样问题的分布式算法与分布式计算复杂性受到越来越多的关注。近年来，有一系列的工作对分布式采样理论展开系统性的研究。综述了分布式采样的重要结论，主要包括有严格理论保障的分布式采样算法、采样问题在分布式模型上的计算复杂性以及采样与推断等问题在分布式计算模型中的相互联系。

自旋系统是统计物理学中用来描述微观粒子相互作用的重要框架,其可以描述伊辛模型,硬核模型,玻茨模型等统计物理学中的重要模型;通过求解自旋系统的配分函数可以得出物质的能量、磁矩等物理性质.作为一种重要的图模型,自旋系统在理论计算机、人工智能、概率论等领域中被称作马尔可夫随机场而广泛应用,其可以描述着色问题、图同态问题等图论中的重要问题.对图中的点和边赋予非负权重,自旋系统可以诱导出著名的吉布斯分布;配分函数的近似计算可以归约到对应的吉布斯采样问题,通过吉布斯采样可以求解系统的相关物理性质和统计规律。该文章研究树结构上自旋系统的快速采样算法。

双态自旋系统是统计物理学在处理互作用粒子系统时所建立的简化模型,计算该系统的配分函数(partition function)在统计物理及计算机科学中均有重要意义。对于一般的系统,配分函数的精确计算已被证明是＃P难的,但其是否能被高效地近似计算一直是理论计算机科学关注的问题。近年来,这一领域取得了较大的突破。研究者建立了配分函数的可近似性与该物理系统相变的联系,并且在很大的参数范围内理解了可近似性。文中对铁磁性双态自旋系统配分函数的可近似性研究进行了综述,介绍了目前针对该问题设计近似算法的三类技巧的主要思想,并把这些算法的结果与该问题在不可近似方面的结果进行了比较。