研究在稀疏的 Erdős-Rényi 随机图中寻找大独立集的算法任务，其中低次多项式算法可以找到半优大小的独立集，但不大于此规模。

Oct, 2020

本研究证明：在随机图中，最大独立集问题的组合结构会在独立集大小 k 超过 k nln (d)/d 这个点时发生相变，形成一个错综复杂的景象，局部搜索算法难以摆脱。这一现象通过 Metropolis 过程，即一个用于采样独立集的马尔可夫链实现了指数下界。

Jul, 2010

本研究探讨了使用独立集合查询进行图边估计的问题，并提出了两种算法来估计 n 个顶点的图中边的数量。

Nov, 2017

本研究提出了一种基于低度图的层次快速算法，可以在多项式空间复杂度内解决最大独立集问题，并得到了在不同最大度的图形中最大独立集问题的改进算法。

Dec, 2013

本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。

Jul, 2019

该论文研究了 $n$ 个顶点的图的退化度，提出了基于 Bron-Kerbosch 算法的近似最优固定参数可跟踪算法，用以枚举所有最大团，并给出算法的时间复杂度、最大团的数量及匹配的上下界。

Jun, 2010

本文通过研究 n 维立方体图中每个 $(2^{n-1}+1)$- 顶点诱导子图的最大度数，证明了布尔函数的灵敏度和度数之间存在多项式关系，从而解决了一个理论计算机科学中的基础性问题：感度猜想。

Jul, 2019

研究在随机图 G (n,p) 上的独立数和色数及其相应的松弛值，提出了一种改进的算法来近似计算独立数，同时对于判断 G (n,p) 是否可着色的算法提出了改进方法，并计算了边概率 p 范围内松弛值的渐近值。

Jun, 2003

本文研究了在给定概率分布 P（{0,1}^n 上），并具有样本访问的情况下，测试潜在贝叶斯网络的最大入度的问题。研究表明，该问题的样本复杂度为 Θ(2^(n/2)/ε^2) 。我们的算法依赖于先前用于获得样本最优测试器的测试通过学习框架；为了应用该框架，我们开发了新的算法来进行 “近似适当” 的贝叶斯网络学习，并在 χ^2 差异下高概率学习，这具有独立兴趣。

Apr, 2023

本文提出一种基于图分割和并行二分图最大匹配的高效并行核化算法，通过依赖检查和约简跟踪技术加速核化，能够同时快速生成小内核，以及找到最小内核并加速发现最大独立集，取得比现有最快算法更小的内核大小和类似执行时间的优势。

Aug, 2017