**Definition 1**
A fan-in

*n* gate is an

*n*-variable Boolean function. Let

be gates of unbounded fan-in. Then a

denotes a depth-

circuit with a

*G*_{1}-gate on the top,

*G*_{2} gates on the second level,

*G*_{3} gates on the third level from the top,..., and

gates on the last level. Multi-linear polynomials of input-variables

of degree at most

*d* are connected to

gates on the last level. The size of a circuit is defined to be the total number of the gates

in the circuit.

**Definition 3**
Let

*p* and

*q* be two different primes, and let

*d* be a non-negative integer. Then

denotes a

circuit, where the input of each

-gate is a polynomial, which can be computed by an arithmetic circuit with arbitrarily many ADDITION gates of unbounded fan-in and with at most

*d* fan-in 2 MULTIPLICATION gates.