- 量子机器学习的阴影
本文提出了一种基于量子线性模型和经典影子重构的方法来构建可在经典计算机上运行的量子机器学习模型，从而绕过访问量子计算机的需要，并对可实现经典阴影模型的学习任务及其复杂性进行了讨论。
- ACL并行权衡：Log-Precision Transformer 的局限性
本研究证明了计算精度对数与输入标记数量相关的 transformer 神经网络可以通过常深度对数空间均匀阈值电路进行模拟，并且从复杂性理论的角度提供了关于 transformer 网络计算力的见解，这表明如果 L≠P，那么 transfor - 结果不可区分性
该研究通过利用复杂性理论和加密学中发展的计算不可区分性来引入结果不可区分性，调查了一系列结果不可区分性定义的等级，其严格程度随着区分器可以访问的预测器的程度而增加，并发现结果不可区分性在定性上与先前研究的不可区分性概念有所不同，从而为政治争 - 具有亚线性时间预处理的确定性点过程的精确采样
研究了确定性点过程的复杂性，提出了一个新的采样算法，其中预处理成本为 n*poly (k)，采样成本为 poly (k)。
- 精确黑盒分析下的最优参数选择
本文通过提出多个变量漂移定理，证明了使用一种新的 (1+1)- 型算法以及具有适应性变异强度的做法来解决 OneMax 问题所需的运行时间为 n ln (n) - cn ± o (n)，并在固定预算视角下找到相对于已有算法最优解约高 13% - 离散黑盒优化启发式的复杂性理论
研究演化算法的理论，尤其是随机黑盒优化技术理论中占主导地位的一个话题是运行时间分析，它旨在通过限制启发式算法在给定问题上需要的函数评估次数来理解其性能，并通过复杂性理论来研究算法解决问题的极限。该论文从黑盒优化的角度回顾了文献中提出的不同的 - 参数化 Markov 链：PCTL 复杂度和无分式高斯消元
本文研究了参数化马尔可夫链的一些任务，包括计算可达性概率和符号表示，提出了一种方法来提高计算有理函数的实现，同时，对参数化马尔可夫链和概率计算树逻辑的模型检查问题进行了复杂度理论讨论，得出了多项式和指数时间算法的边界。
- 量子霸权实验的复杂性理论基础
本文针对量子计算机的性能和量子电路等问题，探讨了量子优越性、采样、复杂度等方面的理论基础及相关算法，并展示了量子优越性相对于多项式层次、BPP、BQP 等的可行性及其假设。
- 使用少量线性查询解决 $k$-SUM 问题
本文研究 $k$-SUM 问题，在复杂度理论、算法、线性查询和决策树等方面取得了一些成果，并提供了一种新型随机算法，其运行时间类似于已知算法但是线性查询次数是独立于 $k$ 的多项式而不再是上限。
- 独立随机变量多项式的反集中
该研究论文的主要研究领域和主题为：独立随机变量的多项式抗集中性质证明、计算机复杂度理论中的下界问题和随机图中固定图的数量的反集中性结论。
- 稀疏线性回归问题多项式时间算法性能下界
通过复杂性理论的标准假设（NP 不在 P/poly），我们证明了稀疏线性回归的极小化预测风险可以由多项式时间算法实现，但实际上实现优化算法时，二者之间存在差距。特别是在设计矩阵不良条件下，多项式时间算法可以实现的极小化预测损失可能会明显高于 - 稀疏主成分分析的计算下界
在稀疏主成分检测的背景下，我们提供了计算效率的统计代价存在的证据。我们通过检测它能够检测到的最小信号强度来测量测试性能，并提出了一种基于半定规划的计算有效方法。同时，我们证明了这个测试的统计性能不能被任何计算有效的方法严格改进。我们的结果可 - 选举操纵问题中的搜索与决策
本研究发现，在大多数情况下，选举操纵和选举管理的控制可以在多项式时间内成功实现，但生成成功的操纵行为可能需要超出多项式时间。
- 随机凸优化的预言机复杂度信息论下界
本文研究使用计算机预测的随机凸优化的复杂性，提出了改善已知结果的方法，并获得了各种函数类的紧致极小复杂度估计。
- 经典计算、量子计算和 Shor 因式分解算法
本文介绍了量子计算的主要问题和算法，包括量子并行性和初始化、基于经典布尔函数的量子计算、量子傅里叶变换、Grover 搜索算法和 Shor 分解算法，以及与可计算函数的谱特性相关的 Kolmogorov 复杂度。