.png){kind=icon}
.png){kind=icon}
Return
Symmetric Arithmetic Circuits
.png){kind=icon}
PRE
AI
DOI：10.4086/toc.2025.v021a014.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
arithmetic circuits
algebraic circuits
symmetric circuits
determinant
permanent
lower bounds
descriptive complexity
circuit complexity
matching