We investigate the computational power of depth two circuits
consisting of $MOD^r$--gates at the bottom and a threshold gate at
the top (for short, threshold--$MOD^r$ circuits) and circuits with
two levels of $MOD$ gates ($MOD^{p}$-$MOD^q$ circuits.) In particular, we
will show the following results
(i) For all prime numbers $p$ and integers $q,r$ it holds that
if $p$ divides $r$ but not $q$ then all threshold--$MOD^q$ circuits
for $MOD^r$ have exponentially many nodes.
(ii) For all integers $r$ all problems computable by depth two $\{AND,OR,NOT\}$--circuits of (quasi) polynomial size can be represented by threshold--$MOD^r$ circuits with (quasi)poly\-no\-mially many edges.
(iii) There is a problem computable by depth three $\{AND,OR,NOT\}$--circuits
of linear size and constant bottom fan--in which for all $r$ needs
threshold--$MOD^r$ circuits with exponentially many nodes.
(iv) For $p,r$ different primes, and $q\geq 2,$ $k$ positive integers,
where $p$ does not divide $q,$
every $MOD^{p^k}$-$MOD^q$ circuit for $MOD^r$ has exponentially many nodes.
Results (i) and (iii) imply the first known exponential lower bounds on the
number of nodes of threshold--$MOD^r$ circuits, $r\neq 2$.
They are based on a new lower bound method for the representation
length of functions as threshold functions over predefined
function bases, which, in contrast to previous related techniques
works even if the
edge weights are allowed to be unbounded and if the bases are nonorthogonal.
The special importance of result (iii) consists in the fact that the known
spectral--theoretically based
lower bound methods for threshold--$XOR$ circuits can provably
not be applied to
$AC_0$--functions. Thus, by (ii), result (iii) is quite sharp and gives a
partial (negative) answer to the
(open) question whether there exist simulations of $AC_0$--circuits
by small depth threshold circuits which are more efficient than that
given by Yao's important result that $ACC^*\subseteq TC_{0,3}^*$ [Y90].
Finally we observe that our method works also for
$MOD^{p}$-$MOD^q$ circuits, if $p$ is a power of a prime.
