最大割和最小特征值
该论文研究了高阶重复本征值与稀疏割的关系，探讨了利用底部 k 个本征向量将顶点嵌入到 R^k 中，并应用几何考虑进行嵌入的聚类算法的理论基础，并证明了在所有图形中，存在一组大小不超过 2n/k 的集合，其扩展至多为 O (sqrt (λklogk))，从理论上提供了这些算法的近乎最优权衡。
Nov, 2011
本文通过分布式算法研究了在标准同步消息传递模型下，计算近似的最小边割问题，提出了随机分层技术作为分析随机边采样的一种简单方法，并给出了两个分布式算法的时间复杂度，同时还强化了上一篇研究的下界。
May, 2013
本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法，解决了设计拥有近似保证的局部图聚类算法的开放性问题，并且其近似保证与 Cheeger 不等式相当。
Apr, 2012
在半随机图模型中，我们研究了平衡切割问题的精确性和时间复杂度，并且提出了第一个近似线性时间算法，以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间 O (1) 近似的方法。
Jun, 2024
本篇研究将提出一种计算效率更高的算法来构建图的 $(1 + ϵ)$- 频谱稀疏子图，该算法基于三种新技术，并使用新的潜力函数，通过半定规划求解构造单侧频谱稀疏子图。
Feb, 2017
介绍了一个广义图拉普拉斯算子，旨在研究超图的特定组合属性，如多路扩展和直径，并使用扩散过程和程序化最小化器来优化 Cheeger 不等式和 k-th 程序化最小化器。
May, 2016
研究 Bilu 和 Linial 提出的稳定性概念，提出了一个基于半定编程的精确多项式算法解决具有 γ 稳定性的 Max Cut 问题，对于 γ <α_SC (n/2) 的情况，不存在可解决的凸松弛方法，此外还研究了最小多路径切问题的 4 - 稳定性。
May, 2013