Representations of boolean functions as polynomials (over rings) have
been used to establish lower bounds in complexity theory. Such
representations were used to great effect by Smolensky, who
established that MOD q \notin AC^0[MOD p] (for distinct primes p, q)
by representing AC^0[MOD p] functions as low-degree multilinear
polynomials over fields of characteristic p. Another tool which has
yielded insight into small-depth circuit complexity classes is the
program-over-monoids model of computation, which has provided
characterizations of circuit complexity classes such as AC^0 and NC^1.

We introduce a new model of computation, the polynomial program, which
naturally unifies both the polynomial (over ring) model of computation
and the program-over-monoids model of computation. Our motivation is
to extend Smolensky's result to prove AC^0[MOD m] lower bounds, where
m is a composite with at least two distinct prime factors.

In this paper, we first study the basic properties of this new model
of computation and its relationship to previous work. Then, we show
that Smolensky's proof of the ``hardness'' of certain functions for
the polynomial model of computation has an analog in the polynomial
program model. We also prove a dichotomy theorem on finite groups,
essentially showing that a finite group G either is so
``complicated'' that every boolean function has a degree one
polynomial program over G, or is too ``simple'' in that the function
MOD p can be computed by a low-degree polynomial program over G
for at most one prime p. The property of nilpotence gives the
dividing line. This dichotomy theorem rigorously demonstrates
limitations of the Razborov-Smolensky method for polynomial programs
over finite groups.