next up previous
Next: The Degree-Decreasing Lemma Up: A Degree-Decreasing Lemma for Previous: Introduction

Preliminaries

Definition 1   A fan-in n gate is an n-variable Boolean function. Let $G_1,G_2,\ldots,G_\ell$ be gates of unbounded fan-in. Then a

\begin{displaymath}(G_1,G_2,\ldots,G_\ell; d)-\hbox{ circuit}\end{displaymath}

denotes a depth-$\ell$ circuit with a G1-gate on the top, G2 gates on the second level, G3 gates on the third level from the top,..., and $G_\ell$ gates on the last level. Multi-linear polynomials of input-variables $x_1,x_2,\ldots,x_n$ of degree at most d are connected to $G_\ell$ gates on the last level. The size of a circuit is defined to be the total number of the gates $G_1,G_2,\ldots,G_\ell$ in the circuit.

All of our gates are of unbounded fan-in, and we allow to connect inputs to gates or gates to gates with multiple wires. Let us note, that we get an equivalent definition, if we allow AND gates of fan-in at most d on the bottom level, instead of degree d multi-linear polynomials. In the literature MODm gates are sometimes defined to be 1, iff the sum of their inputs is divisible by m, and sometimes they are defined to be 1, iff the sum of their inputs is not divisible by m. The following, more general definition covers both cases.

Definition 2   We say that gate G is a MODm-gate, if there exists a non-empty $A\subset\{0,1,\ldots,m-1\}$, $A\neq \{0,1,\ldots,m-1\}$ such that

\begin{displaymath}G(x_1,x_2,\ldots,x_n)=\cases{1, \hbox{ if } \sum_{i=1}^nx_i \bmod{m}\in A\cr
0 \hbox{ otherwise.}}\end{displaymath}

$A\subset\{0,1,\ldots,m-1\}$ is called the 1-set of G. MODm gates with 1-set A are denoted by MODAm.

Definition 3   Let p and q be two different primes, and let d be a non-negative integer. Then

\begin{displaymath}(\hbox{\rm MOD}_q,\hbox{\rm MOD}_p;d-\hbox{\rm AND})\end{displaymath}

denotes a $(\hbox{\rm MOD}_q,\hbox{\rm MOD}_p;d+1)$ circuit, where the input of each $\hbox{\rm MOD}_p$-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.

For example, the determinant (or the permanent) of a t x t matrix with entries zij can be computed by t2-1 MULTIPLICATION-gates, each with fan-in 2. Each polynomial, which can be computed by arbitrarily many ADDITION gates and at most d fan-in 2 MULTIPLICATION gates has degree at most d+1. However, the converse is not true. This can be seen by considering the degree-2 polynomial $x_1y_1+x_2y_2+\cdots+x_ny_n$ over GF(2), which has high communication complexity [5], while polynomials which are computable by d fan-in 2 MULTIPLICATION gates have low communication complexity for small d's .
next up previous
Next: The Degree-Decreasing Lemma Up: A Degree-Decreasing Lemma for Previous: Introduction
Vince Grolmusz
1999-11-08