Theorem 9
Suppose, that function
can be computed by a
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
circuit of size

(p^{2d}+1)s.

Proof: We first show, that our
circuit of size s can be converted into a
circuit of size at most p^{2}s+1. Repeating this conversion d-1 times, the statement follows.
We know that the input of every
-gate can be constructed with at most d multiplication in an arithmetic circuit. Lets consider a fixed
-gate. Suppose, that the last multiplication, which computes its input-polynomial is ,
where
are multi-linear polynomials of n variables. This
-gate, using the Degree Decreasing Lemma (Lemma 4), can be converted to at most p^{2}
-gates, each with inputs, constructible with at most d-1 multiplications, plus (possibly) a leftover
-gate with input 1 (which may be connected to the
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
-gates, the result is a
circuit of size at most p^{2}s+1, since the ``leftover''
-gate with input 1 should be counted once.
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:Bibliography Up:Applications of the Degree Previous:The MOD r functionVince Grolmusz 1999-11-08