Lower Bounds for Symmetric Circuits for the Determinant
Lower Bounds for Symmetric Circuits for the Determinant
复制标题
行列式对称电路的下界
DOI：
10.4230/lipics.itcs.2022.52
复制
发表时间：
2021
影响因子：
5.6
通讯作者：
G. Wilsenach
中科院分区：
文献类型：
--
作者：
A. Dawar;G. Wilsenach
Dawar和Wilsenach（ICALP 2020）介绍了对称算术电路的模型，并展示了用于计算行列式和永久式的对称电路的大小之间的指数分离。对称性限制是，采用矩阵输入的电路不受同时应用于矩阵的行和列的置换的影响。在这样的限制下，我们有多项式大小的电路计算行列式，但没有次指数大小的电路永久。在这里，我们考虑一个更严格的对称性要求，即电路是不变的任意偶排列分别适用于行和列，并证明了一个指数下界，甚至电路计算的行列式。结果需要大量的新机制。我们开发了一个通用的框架，证明下界的对称电路限制对称性，基于一个新的支持定理和新的两个球员限制双射游戏。这些都适用于行列式问题的一种新的建设矩阵的双邻接矩阵的图形的基础上的CFI建设。我们的一般框架开辟了探索各种对称性限制和研究对称性和算术电路使用的其他资源之间的权衡。
Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithmetic circuits and show an exponential separation between the sizes of symmetric circuits for computing the determinant and the permanent. The symmetry restriction is that the circuits which take a matrix input are unchanged by a permutation applied simultaneously to the rows and columns of the matrix. Under such restrictions we have polynomial-size circuits for computing the determinant but no subexponential size circuits for the permanent. Here, we consider a more stringent symmetry requirement, namely that the circuits are unchanged by arbitrary even permutations applied separately to rows and columns, and prove an exponential lower bound even for circuits computing the determinant. The result requires substantial new machinery. We develop a general framework for proving lower bounds for symmetric circuits with restricted symmetries, based on a new support theorem and new two-player restricted bijection games. These are applied to the determinant problem with a novel construction of matrices that are bi-adjacency matrices of graphs based on the CFI construction. Our general framework opens the way to exploring a variety of symmetry restrictions and studying trade-offs between symmetry and other resources used by arithmetic circuits.
登录
查看更多内容
对称计算（特邀报告）
DOI：
--
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Anuj Dawar
通讯作者：
Anuj Dawar
影响因子：
0.5
作者：
Anderson M
通讯作者：
Anderson M
论对称线性规划的威力
DOI：
10.1109/lics.2019.8785792
发表时间：
2019
期刊：
--
影响因子：
--
作者：
Atserias A
通讯作者：
Atserias A
DOI：
--
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Anuj Dawar
通讯作者：
Anuj Dawar