行列式对称电路的下界

《ACM Transactions on Computation Theory》：Lower Bounds for Symmetric Circuits for the Determinant

　　

摘要AI 摘要

要查看此 AI 生成的摘要，您必须拥有高级访问权限。

了解更多登录

摘要

摘要

Dawar 和 Wilsenach（《计算理论》2025 年）提出了对称算术电路模型，并证明了用于计算行列式与用于计算积和式的对称电路之间的大小存在指数级分离。对称限制是指：接收矩阵输入的电路在同时对该矩阵的行和列施加置换时保持不变。在这样的限制下，我们拥有计算行列式的多项式大小电路，但没有亚指数大小电路可计算积和式。在本文中，我们考虑一种更为严格的对称要求，即电路在分别对行和列施加任意偶置换时保持不变，并证明即使对于计算行列式的电路也存在指数级下界。我们发展了一种通用的下界证明框架，用于具有受限对称性的对称电路，该框架基于一个新的支撑定理和新的双玩家受限双射博弈。这些成果被应用于行列式问题，其中涉及一种新颖的矩阵构造，这些矩阵是基于 CFI 构造的图的邻接矩阵。我们的通用框架为探索各种对称限制以及研究对称性与算术电路所使用的其他资源之间的权衡开辟了一条道路。

AI 摘要

AI 生成摘要（实验性）

本摘要使用自动化工具生成，并非由文章作者撰写或审核。提供本摘要是为了支持文献发现，帮助读者评估相关性，并协助来自相邻研究领域的读者理解该工作。本摘要旨在补充作者提供的摘要，后者仍然是论文的主要摘要。全文仍然是权威的正式版本。 点击此处了解更多。

点击 此处 对此摘要的准确性、清晰度和有用性进行评论。这样做将有助于改进未来重新生成的版本。

要查看此 AI 生成的通俗语言摘要，您必须拥有高级访问权限。