Smaller ACC0 Circuits for Symmetric Functions

Brynmor Chapman, Ryan Williams

What is the power of constant-depth circuits with $MO{D}_m$ gates, that can count modulo $m$? Can they efficiently compute MAJORITY and other symmetric functions? When $m$ is a const…