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

The Proof of Theorem 9

Theorem 9   Suppose, that function $f:\{0,1\}^n\to\{0,1\}$ can be computed by a $(\hbox{\rm MOD}^B_q,\hbox{\rm MOD}^A_p;d-\hbox{\rm AND})$ circuit of size s, where p and q are two different primes, and d is a non-negative integer. Then f can also be computed by a $(\hbox{\rm MOD}^B_q,\hbox{\rm MOD}^A_p;1)$ circuit of size

(p2d+1)s.

Proof:    We first show, that our $(\hbox{\rm MOD}^B_q,\hbox{\rm MOD}^A_p;d-\hbox{\rm AND})$ circuit of size s can be converted into a $(\hbox{\rm MOD}^B_q,\hbox{\rm MOD}^A_p;(d-1)-\hbox{\rm AND})$ circuit of size at most p2s+1. Repeating this conversion d-1 times, the statement follows. We know that the input of every $\hbox{\rm MOD}^A_p$-gate can be constructed with at most d multiplication in an arithmetic circuit. Lets consider a fixed $\hbox{\rm MOD}^A_p$-gate. Suppose, that the last multiplication, which computes its input-polynomial is $\Phi\Psi+\Xi$, where $\Phi,\Psi,\Xi$ are multi-linear polynomials of n variables. This $\hbox{\rm MOD}^A_p$-gate, using the Degree Decreasing Lemma (Lemma 4), can be converted to at most p2 $\hbox{\rm MOD}^A_p$-gates, each with inputs, constructible with at most d-1 multiplications, plus (possibly) a leftover $\hbox{\rm MOD}^A_p$-gate with input 1 (which may be connected to the $\hbox{\rm MOD}^B_q$ gate with multiple wires) such that the sum of these gates give the same output modulo q as the original one. If the conversion is done for all $\hbox{\rm MOD}^A_p$-gates, the result is a $(\hbox{\rm MOD}^B_q,\hbox{\rm MOD}^A_p;(d-1)-\hbox{\rm AND})$ circuit of size at most p2s+1, since the ``leftover'' $\hbox{\rm MOD}^A_p$-gate with input 1 should be counted once. $\Box$ Acknowledgment. The author is indebted to Dániel Varga for suggesting an improvement on the original version of Definition 3, and for Katalin Friedl, Zoltán Király, and Gábor Tardos for fruitful discussions on this work. Supported in part by grants OTKA F014919, FKFP 0835, AKP 9756.
next up previous
Next: Bibliography Up: Applications of the Degree Previous: The MOD r function
Vince Grolmusz
1999-11-08