We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of
a class of high-degree polynomials that can be simulated via arithmetic circuits of much lower degree.

Some minor errors are corrected, and the exposition is clarified in a few places.

We consider the complexity class ACC^1 and related families of arithmetic circuits. We prove a variety of collapse results, showing several settings in which no loss of computational power results if fan-in of gates is severely restricted, as well as presenting a natural class of arithmetic circuits in which no expressive power is lost by severely restricting the algebraic degree of the circuits. We also give characterizations of ACC^1 and TC^1 in terms of circuits consisting only of MOD gates. These results tend to support a conjecture regarding the computational power of the complexity class VP over finite algebras, and they also highlight the significance of a class of arithmetic circuits that is in some sense dual to VP.

There was a mis-statement in Proposition 2; see Proposition 3 and Corollary 2 in the new version.
Several results have been strengthened, including Corollaries 3 and 5, and Theorems 7 and 10. Various improvements have been made to the presentation and exposition.

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of
a class of high-degree polynomials that can be simulated via arithmetic circuits of much lower degree.