On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols

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 give a new simulation of semi-unbounded Boolean circuits by semiunbounded circuits with unbounded parity gates. Our simulation is simpler and more efficient with respect to depth than the original simulation of G'al and Wigderson [4]. 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 [3]. 1 Introduction We present two randomized simulations of Boolean computational models by their corresponding "parity" models. The first results of this kind are due to [5, 4], who pr..