论文标题
对称算术电路
Symmetric Arithmetic Circuits
论文作者
论文摘要
我们引入了对称算术电路，即具有自然对称性限制的算术电路。在计算变量矩阵上定义的多项式的电路中，诸如决定符或永久性的矩阵中，限制量相当于要求电路的形状在矩阵的同时行和列排列下不变。我们建立了用于计算永久性的任何对称电路的大小上的无条件指数下限。相反，我们表明有多项式大小的对称电路用于计算特征零字段的决定因素。
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.
