本文通过提出多个变量漂移定理，证明了使用一种新的 (1+1)- 型算法以及具有适应性变异强度的做法来解决 OneMax 问题所需的运行时间为 n ln (n) - cn ± o (n)，并在固定预算视角下找到相对于已有算法最优解约高 13%。

Jul, 2018

本文提出了一种新的黑盒优化模型 —— 精英黑盒模型，该模型要求算法的所有决策只基于到目前为止采样的固定数量的最佳搜索点，通过实例测试证明，精英黑盒复杂度可以比以前所有黑盒模型的相应复杂度更接近典型进化算法的运行时间，并引入了 $p$-Monte Carlo 黑盒复杂度的概念。

Aug, 2015

本文介绍了通过量子查询和量子示例从学习布尔函数的算法的复杂性的新结果，其中我们探讨了中间问题的量子和经典查询复杂度与精确学习问题和谐平衡的自然问题，并提高了期望严格学习的新下界，以达到经典 PAC 学习的已知上界。

Nov, 2004

本论文旨在寻找用于黑盒优化的最佳算法，研究表明 Metropolis 算法在求解 DLB 问题时表现最佳，并且比所有其他算法都要快。

Sep, 2021

通过使用标准约减和新技术的混合方法，我们改进了查找凸集中点的运行时间，同时提高了在连续和组合优化中的算法性能，特别是子模规划和半定规划问题。

Aug, 2015

证明了在比特复杂度模型下倍增 n 位整数的成本的 Furer 界限，并提出了一种比 Furer 算法更快的新算法。

Jul, 2014

该论文通过限制阿贝尔群中三色无和集的大小，阐述了如何从阿贝尔群中获取矩阵乘法乘积的指数 $ω=2$ 的具体猜想，从而得出这一框架无法获得 $ω=2$ 的结论，并证明了 Tao 提出的张量秩的一个变体可以量化几何不变理论中的不稳定张量的概念。

May, 2016

研究演化算法的理论，尤其是随机黑盒优化技术理论中占主导地位的一个话题是运行时间分析，它旨在通过限制启发式算法在给定问题上需要的函数评估次数来理解其性能，并通过复杂性理论来研究算法解决问题的极限。该论文从黑盒优化的角度回顾了文献中提出的不同的黑盒复杂性模型，并对这些模型的界限进行了调查，探讨了运行时间分析和黑盒复杂性的相互作用如何启发演化计算中已经研究的问题的新算法解决方案，并讨论了未来工作的若干有趣的开放性问题。

Jan, 2018

我们对 Ben-David、Kushilevitz 和 Mansour (1997) 的可逆在线学习设置中学习者错误的数量提出新的上界和下界。定性地，我们证明了一个三分法，即随着 n 的增长，学习者所犯错误的最小数量只能取三个明确定义的值之一：n，Θ(log (n)) 或 Θ(1)。此外，这种行为是由 VC 维度和 Littlestone 维度的组合确定的。定量地，我们展示了各种将错误数量与众所周知的组合维度相关联的界限。特别地，我们将 Θ(1) 情况下的常数的已知下界从 Ω(√log (d)) 改进为 Ω(log (d))，其中 d 是 Littlestone 维度。最后，我们将我们的结果扩展到多类分类和不可知设置。

Nov, 2023

使用有噪声的查询计算具有错误概率的函数问题，给出了计算 OR 函数和 MAX 函数所需的期望查询次数，并在两个函数的上下界中对错误概率进行了更紧密的依赖。

Sep, 2023