next up previous
Next: The MOD r function Up: Applications of the Degree Previous: Constant Degree Hypothesis

The ID function

Krause and Waack [13], using communication-complexity techniques, showed that any $(\hbox{\rm MOD}^{\{1,2,\ldots,m-1\}}_m,\hbox{\rm SYMMETRIC};1)$ circuit, computing the ID function:

\begin{displaymath}\hbox{\rm ID}(x,y)=\cases{1,\hbox{ if } x=y,\cr
0 \hbox{ otherwise,}}\end{displaymath}

for $x,y\in\{0,1\}^n$, should have size at least $2^n/\log m$, where SYMMETRIC is a gate, computing an arbitrary symmetric Boolean function. Using this result, we prove:

Theorem 7   Let p and q be two different primes. If a

\begin{displaymath}( \hbox{\rm MOD}^{\{1,2,\ldots,m-1\}}_q, \hbox{\rm MOD}^A_p, (1-\varepsilon) n-\hbox{\rm AND})\end{displaymath}

circuit computes the 2n-fan-in ID function, then its size is at least $2^{c\varepsilon n}$, where 0<c<1 depends only on p.

Proof:    From the result of [13] and from Theorem 9 the statement is immediate. $\Box$ Unfortunately, the methods of [13] do not generalize for MODBq gates with unrestricted B's.

Vince Grolmusz