分离边界：近似深度3电路的指数间隔扇入层级定理

《Journal of the ACM》：Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits

　　摘要Mulmuley 和 Sohoni（2001）提出了一个雄心勃勃的纲领，称为**几何复杂性理论**（GCT），旨在利用代数几何和表示论来证明 P ≠ NP 及相关猜想。GCT 逐渐在复杂性理论中引入了新的结构和问题。GCT 试图通过定义**边界类**来捕捉代数/几何意义上的"逼近"概念。令人惊讶的是，（Kumar, ToCT'20）证明了顶层扇入为 2 的深度-3 电路的边界具有通用能力（即 Σ2ΠΣ?），这与其经典模型形成了鲜明对比。最近，（Dutta, Dwivedi, Saxena, FOCS'21）给出了一个上界，证明有界顶层扇入的边界深度-3 电路（Σ?ΠΣ?，其中 k 为常数）可以由多项式大小的代数分支程序（ABPs）来计算。但证明 ABPs 类与 Σ?ΠΣ? 之间的**指数级**分离仍然是一个开放问题。在本文中，我们证明了任意两个相邻边界类 Σ?ΠΣ? 和 Σ??1ΠΣ? 之间的强指数级分离，从而建立了常数顶层扇入的边界深度-3 电路的**最优层次结构**。用 GCT 的语言来说，我们证明了 F??1 的 Chow 簇的**填充 k 阶割线簇**的指数级层次结构。这正面回答了 [Dutta, Dwivedi, Saxena, FOCS'21 中的开放问题 2] 以及 [Landsberg, Annal. Ferrara'15 中的问题 8.10（其中 r 为常数）]。---AI 摘要（实验性）本摘要由自动化工具生成，并非由本文作者撰写或审核。提供此摘要是为了支持文献检索，帮助读者评估相关性，并协助来自相邻研究领域的读者理解本文。本摘要旨在补充作者提供的摘要，后者仍然是本文的主要摘要。全文仍然是权威的正式版本。[点击此处了解更多关于 ACM AI 摘要的信息]。点击[此处]对本摘要的准确性、清晰度和实用性发表评论。这样做将有助于改进未来重新生成的版本。要查看此 AI 生成的通俗摘要，您必须拥有高级访问权限。