We investigate the computational power of depth two circuitsconsisting of MODr--gates at the bottom and a threshold gate atthe top (for short, threshold--MODr circuits) and circuits withtwo levels of MOD gates (MODp-MODq circuits.) In particular, wewill show the following results(i) For all prime numbers p and integers qr it holds thatif p divides r but not q then all threshold--MODq circuitsfor MODr have exponentially many nodes.(ii) For all integers r all problems computable by depth two ANDORNOT --circuits of (quasi) polynomial size can be represented by threshold--MODr circuits with (quasi)poly-no-mially many edges.(iii) There is a problem computable by depth three ANDORNOT --circuitsof linear size and constant bottom fan--in which for all r needsthreshold--MODr circuits with exponentially many nodes.(iv) For pr different primes, and q2 k positive integers,where p does not divide q every MODpk-MODq circuit for MODr has exponentially many nodes.Results (i) and (iii) imply the first known exponential lower bounds on thenumber of nodes of threshold--MODr circuits, r=2 .They are based on a new lower bound method for the representationlength of functions as threshold functions over predefinedfunction bases, which, in contrast to previous related techniquesworks even if theedge weights are allowed to be unbounded and if the bases are nonorthogonal.The special importance of result (iii) consists in the fact that the knownspectral--theoretically basedlower bound methods for threshold--XOR circuits can provablynot be applied toAC0--functions. Thus, by (ii), result (iii) is quite sharp and gives apartial (negative) answer to the(open) question whether there exist simulations of AC0--circuitsby small depth threshold circuits which are more efficient than thatgiven by Yao's important result that ACCTC03 [Y90].Finally we observe that our method works also forMODp-MODq circuits, if p is a power of a prime.
展开▼
