研究随机 CSP 问题和多项式时间算法无法寻找解决方案的相位转变，并运用一般技术准确地证明 $k$- 着色的相位转变推出所有已知多项式时间算法的失败点。

Mar, 2008

我们利用统计物理学中的一步副本对称性预测，为所有的 k≥k_0，建立了随机 k-SAT 的可满足性阈值，给出满足阈值和不满足阈值的限制密度的显式计算公式，并用一种新的分析方法对随机图进行矩计算，将一个高维的优化问题映射到了一个更易处理的分析树递归问题，证明了我们的阈值计算方法适用于 1-RSB 普适性类中的各种随机约束满足问题。

Nov, 2014

该论文研究了随机约束满足问题的解空间结构，并证明了在解消失之前，它们会组成指数数量的簇，并且每个簇都相对较小且相距较远。此外，每个簇内的大部分变量都被冻结，并提出 Survey Propagation 算法的一项重要假设。

Nov, 2006

研究二元马尔可夫随机场中，图形选择问题在高维情况下的信息论局限性，为具有最多 k 条边的 p 个定点图的类 $Gpk$ 以及最高 degree 不超过 d 的 p 个定点图的类 $Gpd$，提出了正确图形选择的必要和充分条件，并建立了一个图形译码器，该译码器适用于样本量 n>c'k² log (p) 和 n>c'd³ log (p)。

May, 2009

单指标模型是高维回归问题，根据未知的一维投影通过非线性、潜在非确定性的变换，标签与输入相关，涵盖了广泛的统计推断任务，提供了在高维领域研究统计和计算权衡的丰富模版。我们证明了在统计查询（SQ）和低次多项式（LDP）框架内计算高效算法所需的样本复杂度最低为 Ω(d^k/2)，其中 k 是与模型关联的 “生成” 指数，我们明确定义了这个指数。此外，通过使用部分跟踪算法建立的匹配上界证明了这个样本复杂度也是充分的。因此，我们的结果表明，在 SQ 和 LDP 类中，只要 k>2，计算与统计之间存在明显的差距。为了完成这个研究，我们提供了具有任意大生成指数 k 的平滑和 Lipschitz 确定的目标函数的示例。

Mar, 2024

针对模型类如何拟合标记数据的问题，我们提出了一种计算学习能力的方法，可以使用较小的数据量得出精确结果。该方法也适用于二元分类问题，并在多种真实和合成数据集上得到了验证。

May, 2018

本文提出和研究了一种插入 k-SAT 模型，描述了一个插入分配 σ 和一个具有 k 个文字的子句分布的实例，对于分布复杂性的倒数关联了查询算法的统计下界。该证明引入了一种新的分析统计查询算法的通用技术，并指出了所有种植任务空间中的几何剪枝现象。

Nov, 2013

该研究探讨了如何从动态过程的相关样本中重构二值图形模型，并分析了基于交互筛选目标和条件似然损失的两个估计器的样本复杂性。我们发现，对于来自远离平衡的动态过程的样本，样本复杂度与混合速度快的动态过程相比呈指数级下降。

Apr, 2021

本文探讨了一种利用通用哈希和 SAT 求解器的方法，可以在不牺牲正确性保证的同时，处理具有数十万个变量的公式，解决了人工智能中受限采样和计数的两个基本问题，这对于概率推理及规划，约束随机验证等方面有着广泛应用，并探讨一些需要解决的挑战。

Dec, 2015

研究了在 $k$-SAT 问题中寻找满足分配的算法任务，证明了低次数多项式算法类无法在特定子密度下解决该问题，这是关于任何算法类在与 Fix 相等水平难度下的首个困难结果。

Jun, 2021