该研究讨论了在固定且未知的分布和自然条件下的半空间学习问题，证明了最坏情况下的性能和效率的复杂性。

May, 2015

通过与半空间和所谓的并行煎饼分布的新颖联系，我们以统一的方式获得了较强（而且令人惊讶地简单）的在不适当的情况下学习半空间交集的下界，这是过去几年强大的高维统计学中许多下界构造的核心，我们还给出了统计查询框架下的无条件难度结果。

Feb, 2024

这篇论文介绍了一种新的证明不适当学习难度的技术，基于难以处理的问题的规约，通过与密码假设相结合，发现了学习 $DNF$，半平面和超平面的交集等问题的困难性。

Nov, 2013

学习标签比例 (LLP) 框架在机器学习中日益重要。该研究关注 LLP 学习布尔函数的不可计算性，发现寻找满足 OR 函数一部分常数比例的子集 (包) 的恒定个子句的 CNF 是 NP 困难问题，同时探讨了学习偶函数的可行性，发现利用随机偶算法可以得到近似解。

Mar, 2024

该研究证明了在符合某些要求的示例分布下，多项式的弱会混淆学习几乎不可能，即使在输出更大的概念类的假设的情况下也是如此，这种难度结果从某种程度上包括以前的研究结果，包括最近的对单项式和半空间的适当学习的难度结果。

Dec, 2010

本文提出以布尔规则为基础的分类方法，并通过基于整数规划和 Hamming 距离的算法，寻求简单分类规则和分类准确性之间的平衡，实现优于一级规则的分类效果。

Nov, 2015

本文提出了用于 Disjunctive Normal Form (DNF) 阻塞方案的图论形式化方法，并探究了它们在优化框架中的可学性。此外，作者还简要描述了一个实证案例，该案例概括了本文部分原则。

May, 2016

本文介绍了可分解否定范式（DNNF）作为可行的命题理论形式，并提供了一些在多项式时间内可以执行的强大逻辑操作。在此基础上，本文提出了将任何合取范式（CNF）转化为 DNNF 的算法，并提供其空间和时间复杂度上的结构保证。同时它也介绍了将有序二叉决策图（OBDD）表示的命题理论转换为等价的 DNNF 的线性时间算法。接着，介绍了采用新的操作在 d-DNNF 上遍历之后实现线性时间、完整的信念修正系统。

Mar, 2000

本文探讨了学习线性时序逻辑 (LTL) 公式的计算复杂性，并构建了 LTL 的片段逼近算法，并对许多片段证明了 NP 完全性。

Feb, 2021

本文提出了一种新的问题转化方法，将 CNF 公式的决策问题转化为 Horn 公式的最大可满足性问题，并证明了在鸽笼公式的情况下 MaxSAT resolution steps 的数量存在多项式绑定。

May, 2017