该研究借助 ReLU 挖掘深度学习的奥秘，以布尔函数为背景，考察了 ReLU 网络深度对模型大小的影响，并提出一种随机限制的方法来验证 LTF-OF-RELU 电路的最优性以及 ReLU 深度网络的难以压缩性，并展示出一种 Sum-of-ReLU-of-ReLU 函数实现的不可能性。

Nov, 2017

研究表明，具有指数级有界权重的 poly-size 深度二神经网络不能逼近无法由低次多项式逼近的函数，然而，这些函数可以通过 poly-size 深度三网络逼近，并从均匀分布的角度阐明了深度二和深度三网络之间的区别。

Feb, 2017

研究发现，对于几乎所有已知的激活函数类型，存在简单的（大致上是径向的）函数在 $ eals^d$ 上，可由小型三层前馈神经网络表达，但无法用任何二层网络近似到特定常数精度以上，除非它的宽度在指数级别。此结果证明了深度比宽度对于标准前馈神经网络的提升，即使只增加了 1 层，其价值也可以是指数级别。此外，相比于布尔函数相关研究，该结果需要更少的假设，并且证明技巧和构造方法非常不同。

Dec, 2015

证明了在满足条件的情况下，当用深度为 2 和深度为 3 的神经网络来近似一个在 [0,1]^d 上与 Lipschitz 目标函数的 constant 精度相等的分布时，存在指数级的差距。

Feb, 2024

研究证明利用半代数节点的神经网络比常规 ReLU 节点的神经网络、带 ReLU 和最大化节点的卷积神经网络、乘积求和网络、以及提升的决策树，需要更少的层数和节点才能实现模拟函数。

Feb, 2016

本文证明了：如果基于一颗 treewidth 为 d 的图的量子电路中，其门控运算的总数为 T，则这个电路可以在 T^{O (1)}*exp [O (d)] 的时间里被确定性模拟。此外，本文还证明了：在施加到附近量子比特的约束下，可以高效地模拟对数深度电路。同时，如果随机选择资源并且基于 treewidth 很小的图，则 Raussendorf 和 Briegel 的 one-way 量子计算方案可以有效地被模拟。

Nov, 2005

本文通过利用神经网络和牛顿多面体之间的对偶性，基于 tropical geometry 理论，证明了单层 ReLU 神经网络所能表示的最大值函数类集合随着网络深度的增加而严格扩大，同时允许任意的宽度，且保证网络的权重为整型数。并且，通过对这些 Newton 多面体的归一化面积的奇偶性论证，表明需要层数 $log_2 (n) 向上取整 $ 才能计算 $n$ 个数字的最大值。

Feb, 2023

该论文提出了一种将神经网络转化为特殊形式的二元决策图 (BDD) 的方法，并提出了结合该方法的新提升算法，以及用于计算最终布尔表达式的方法。

Jun, 2023

该论文研究了近期对未知量子电路的可学习性，证明了用于学习量子过程的量子统计查询的自然鲁棒性，并提供了一种有效的方式来评估各种统计噪声，为开发噪声容忍算法提供了强大的框架。我们对具有小的查询复杂度额外开销的常深度量子电路的学习算法进行了适应，并证明了通过统计查询在钻石距离内学习对数和更高深度的随机量子电路的平均情况下的下界。此外，我们展示了从量子统计查询中量子阈值搜索问题的困难性，并讨论了其对浅层量子电路可学习性的影响。最后，我们通过构造一个高效的区分器并证明量子无免费午餐定理的一个新变种，证明了伪随机幺正（PRU）不能使用常深度电路构造。

May, 2024

研究无穷宽度神经网络中的深度分离，该复杂性由权重的整体平方 L2 范数控制（网络中所有权重的平方和）。在以往的深度分离结果中，关注的是宽度方面的分离，这样的结果无法揭示深度是否决定了在网络宽度无限时是否可能学习出具有良好泛化性能的网络。本文研究以学习可行性所需的样本复杂性为标准的分离。具体来说，我们展示了通过由范数控制的深度为 3 的 ReLU 网络以多项式样本复杂度可学习的函数，而由范数控制的深度为 2 的 ReLU 网络无法通过次指数样本复杂度学习相同函数（对于任何范数值）。同时，我们还证明了在反向方向上不可能存在相似的陈述：通过具有无限宽度的范数控制的深度为 2 的 ReLU 网络以多项式样本复杂度可学习的任何函数也可以通过具有范数控制的深度为 3 的 ReLU 网络以多项式样本复杂度学习。

Feb, 2024