Why are mod_m gates interesting? Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's.

What's so special about MOD_m gates?


They allow one to simulate arithmetic over any ring Z_m.
Before Ryan's result, throwing MOD_m gates to the mix gave the first class for which the known lower bounds did not work.


Is there any other natural reason to study MOD_m gates?
$ACC^0$ is a natural complexity class.

1) Barrington showed that computation over non-solvable monoids capture $NC^1$ while over solvable monoids capture $ACC^0$.

2) Recently, Hansen and Koucky  proved  a beautiful result that poly-sized constant width planar branching programs are exactly $ACC^0$. Without the planarity condition, we of course get Barrington's result characterizing $NC^1$. 

So the difference between $ACC^0$ and $NC^1$ is group-theoretic on one hand and topological on the other.

Added: Dana, a simple example of a solvable group is $S_4$, the symmetric group over elements. Without getting into details, any solvable group has a series whose quotients happen to be cyclic. This cyclic structure gets reflected as mod gates while building a circuit to solve word problems over the group. 

On planarity, one would like to believe that planarity may impose restrictions/bottlenecks in the flow of information. This is not always true: for example, variations of planar 3SAT are known to be NP-complete. However, in smaller classes, these restrictions are more "likely" to hold. 

In similar vein, Wigderson showed NL/poly=UL/poly using the isolation lemma. We do not know how to derandomize the isolation lemma over arbitrary DAGs to get NL=UL, but we know how to do so for planar DAGs.