引入了一个理论框架来理解和预测序列分类任务的复杂性，使用布尔函数灵敏度理论的新扩展。在一些 NLP 任务中使用此框架，发现具有挑战性的任务比简单文本分类任务具有更高的敏感度，并且敏感度预测了低敏度解码器的表现。此外，表明高性能的预训练文本表示部分成功的原因是它们提供了低灵敏度解码器可以提取信息的表示形式

Apr, 2021

研究了在积概率空间中具有低影响力函数的问题，证明了具有低影响力和有界次数的多线性多项式的不变性原理，且边际条件下的分布在所有乘积空间中实质上是不变的，从而解决了在理论计算机科学中构建概率可检验证明和经济社会选择理论中的问题。

Mar, 2005

本文考虑了对布尔函数进行随机评估问题，提出了一些近似算法，并基于随机次模集盖问题提出了一种新的适应性双贪心算法，新算法取得了更好的近似度，其中包括线性阈值公式的 3 近似算法，CDNF 公式 (和决策树) 的 O (log kd) 近似算法以及对线性函数的评分算法。

Mar, 2013

本研究主要研究在嘈杂观测下，在图上定义 “爬山友好型” 函数的样本复杂度。作者提出了一个凸性的概念，利用最佳臂识别的变种，可以在少量查询后找到近似最优解。对于具有局部极值并且接近凸性的函数，作者证明了在噪声观测下经典模拟退火的样本复杂度。作者在图基邻近分类和文档重新排序应用问题上，展示了贪心算法和带重启的模拟退火的有效性。

Jun, 2020

对图算法的平均敏感度进行系统研究，并提供了具有低平均敏感度的近似算法，其中主要应用了局部计算算法和已知次线性时间算法的分析方法。

Apr, 2019

本文研究了 submodular functions 可以被其他简单类别的 submodular functions 逼近的程度和方法，并证明了一些上下界。

Apr, 2013

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

Jul, 2019

通过比较查询来优化光滑函数的最佳方法，无需求导方法和梯度计算。

May, 2024

我们研究了分布自由的非参数回归，根据 Ashlagi 等人（2021）提出的一种平均平滑性概念，该概念度量了函数相对于任意未知基础分布的 “有效” 平滑程度。我们提供了分布自由的均匀收敛界限，以及与计算高效的无知学习算法相匹配的采样复杂度。我们的结果表明，最近对于可实现的平滑函数学习所获得的保证可以转移到无知设置中。在我们的证明的核心，我们根据函数类的夹逼熵建立了函数类的均匀收敛速率，这可能具有独立的研究意义。

Sep, 2023

本文提出了一种利用概率多项式计算对数域上任意对称布尔函数并控制误差的低阶多项式方案，借此算法可在超对数维度中在真正的亚二次时间内求解汉明距离，并且能够对内积最大的向量，有最近的 ell1 对和杰卡德系数最大的向量对进行计算。

Jul, 2015