We introduce symmetric arithmetic circuits, i.e. arithmetic circuits with a natural symmetry restriction. In the context of circuits computing polynomials defined on a matrix of variables, such as the determinant or the permanent, the restriction amounts to requiring that the shape of the circuit is invariant under simultaneous row and column permutations of the matrix. We establish unconditional exponential lower bounds on the size of any symmetric circuit for computing the permanent. In contrast, we show that there are polynomial-size symmetric circuits for computing the determinant over fields of characteristic zero.


翻译:我们引入了对称算术电路,即具有自然对称限制的算术电路。在计算变量矩阵中定义的电路中,例如决定因素或永久变量,限制相当于要求电路的形状在矩阵的同步行和列间曲下是无变的。我们在计算永久值时,对任何对称电路的大小设定无条件的指数下下限。相反,我们显示,在计算特性零的字段的决定因素时,存在多数值对称电路。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
已删除
将门创投
4+阅读 · 2019年10月11日
Arxiv
0+阅读 · 2021年3月19日
Arxiv
0+阅读 · 2021年3月17日
Arxiv
0+阅读 · 2021年3月16日
VIP会员
相关资讯
已删除
将门创投
4+阅读 · 2019年10月11日
Top
微信扫码咨询专知VIP会员