- 多项式时间中学习任意温度下的量子哈密顿量
我们研究了使用已知逆温度下 Gibbs 状态的哈密顿量，学习局部量子哈密顿量 H 的问题。我们解决了这个大问题，提出了一种多项式时间算法，通过多项式数量的 Gibbs 状态精确学习到精度为 ε 的哈密顿量 H。
- 二进制估值中存在的 EFX 分配
我们研究公平分配问题和满足公平性准则的 EFX 分配的存在性。通过使用完全不同的技术，我们将这个存在性结果推广到一般的二元估值，并提出了一种多项式时间算法来计算 EFX 分配。
- 0-1 损失线性分类问题的高效可证算法
本研究基于增量单元枚举（ICE）算法，详细介绍了一种可以在多项式时间内精确解决 0-1 损失线性分类问题的算法，据我们所知，这是该旷古难题的第一个经过严格证明的多项式时间算法。
- 寻找不连贯 Horn 表达式的共同点
研究在与人共存的环境中操作的自主系统需要遵循其所处社会的规则。通过在 Horn 表达式的类上识别三个充分条件，我们提供了一个计算共同点的多项式时间算法。如果移除其中任何一个条件，则可能不存在较大类别的共同点。
- IJCAI保证最小最大份额：一些代理被落下
本论文提出了一种以人口为基础的近似公平性概念，重点研究了最大最小份额的分配，并证明了在 9 个代理人以内，可以使用多项式时间算法来分配最大最小份额的 $ rac {2}{3} $，从而提高了现有的保证值，并在合成数据上进行了实证实验。
- 在多项式时间内学习两层修正线性单元神经网络
该研究提出了一种基于高斯分布假设的算法，可以在多项式时间内准确地恢复两层神经网络的权重矩阵，即使在存在噪声的情况下。
- 高效学习 Mallows 模型混合
提出了第一个多项式时间算法来确定具有任意常数个分量的 Mallows 模型的学习参数。同时，通过分析和限制，研究了学习混合 Mallows 模型的复杂性，并展开对改进组成数量依赖性的探索。
- 不可分配公共物品的公平分配
本文研究了公共物品的公平分配问题，提出了一个适用于不可分配公共物品的 “核心” 概念，并引入了一个加性逼近方法和多项式时间算法来处理问题。
- 球形高斯混合物的列表可解鲁棒均值估计与学习
使用多项式技术来移除高维数据集中的异常值，同时提出了非常有效的算法，大大改进了高斯均值估计和学习混合球形高斯问题的保障性能。
- 资源分配博弈中的均衡计算
本文研究了两类经典资源分配博弈的均衡计算问题，提出了一种多项式时间算法来计算这些博弈的纯纳什均衡，并应用于考察单一市场的 Cournot 均衡问题。
- 次二次子模函数最小化
本文通过在 submodular 函数的 Lovasz 扩展上使用投影随机次梯度下降法，利用子模性和数据结构来获得快速的坐标轴下降算法，实现了针对整数值子模函数的超线性 SFM 算法和针对实值子模函数的几乎线性 SFM 算法。
- 修正度数块模型中的社区检测
该研究探讨了在度校正块模型（DCBMs）中进行社区检测的最小极小风险，得出了极小风险是如何和参数相关联的，并提出了一个多项式时间算法来适应性地进行一致和甚至渐近最优的社区检测。
- 优化星型凸函数
该论文介绍了一种多项式时间算法，用于优化无限制的星凸函数，提出了一个随机化算法找到可行域的割面，并强调了该算法的理论吸引力，即在多项式时间算法的范围内引入很多有趣的病态类。
- NIPS稀疏主成分分析的平方和下界
本文研究使用凸松弛法解决高维机器学习问题时，统计与计算的权衡。对稀疏主成分分析（Sparse PCA）问题和 Sum-of-Squares（即 Lasserre / Parillo）凸松弛法进行了探究。通过研究发现基于次数 - 4 的 So - 受限噪音下线性分隔器的高效学习
研究了线性分离器在 Massart 噪声下的可学习性，提供了第一个在此噪声模型下可以多项式时间学习线性分离器的算法，并证明了传统算法不能达到理想误差。我们的算法是基于活动学习的，并且具有对数标签复杂度。
- 通用图模型 MAP 推断的剪枝部分最优化
本文提出了一种新的多项式时间算法来解决最小化无向图模型的能量问题，利用凸松弛方法得到部分最优非松弛积分解，并采用迭代修建策略优化算法，相较之前的方法表现更好。
- 一种用于有损人群恢复的多项式时间算法
本研究基于线性规划和复分析的链接，提出一种 polynomial time algorithm 算法用于解决 lossy population recovery problem，并应用该算法解决了 DNFs 的学习问题。
- 子图稀疏化和近似最优超稀疏化
本文考虑保留原图的一个子图、寻找 k - 边加权图来加强原图的谱稀疏化问题，给出可行条件及多项式时间算法，并在超稀疏化问题和谱优化问题方面得出了应用结果。
- 如何在单纯形上对多项式进行积分
本文解决了有理单纯形上的多项式函数 f 的计算复杂性问题，证明了对于任意多项式都是 NP 难的，但如果多项式仅依赖于有限个变量，则可以在多项式时间内进行积分。
- Twice-Ramanujan Sparsifiers
这篇论文证明了每个图形都有一个谱稀疏器，其边数与其顶点数成线性关系。特别地，通过 Laplacian matrices 构造的谱稀疏器提供了对图形的光谱映射，令其成为扩展图的推广。此外，该论文提供了一个简单的确定性多项式时间算法来构造这种稀