Theory of Computing
-------------------
Title     : Symmetric Arithmetic Circuits
Authors   : Anuj Dawar and Gregory Wilsenach
Volume    : 21
Number    : 14
Pages     : 1-32
URL       : https://theoryofcomputing.org/articles/v021a014

Abstract
--------

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.


--------------

A preliminary version of this paper appeared in the Proceedings of the 47th 
IEEE International Colloquium on Automata, Languages, and Programming (ICALP’20).