TR94-023 Authors: Matthias Krause, Pavel Pudlak

Publication: 12th December 1994 00:00

Downloads: 1357

Keywords:

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.