Lower bounds for modular counting by circuits with modular gates
We prove that constant depth circuits, with one layer of MODm gates at the inputs, followed by a fixed number of layers of MODp gates, where p is prime, require exponential size to compute the MODq function, if q is a prime that divides neither p nor m.
modular counting circuit complexity