We compare two computational models that appeared in the literature in a Boolean setting and in an analog setting based on modular arithmetic. We prove that in both cases the arithmetic version can to some extend simulate the Boolean version. Although the models are very different, the proofs rely on the same idea based on the Schwartz-Zippel-Theorem.

In the first part we prove that depth d semi-unbounded Boolean circuits can be simulated by depth d+O(logd+logn)]]> semi-unbounded arithmetic circuits, regardless of the size. This is an improvement on a similar construction in [#!GalWigderson!#] that achieves depth d+O(logs+logn)]]>, where s is the size of the original circuit. Our construction is simpler and uses fewer random bits. In the second part we prove, that two-party parity communication protocols can approximate nondeterministic communication protocols. A strict simulation of one by the other is impossible as was shown in [#!DKMW97+!#].