  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.
