A note on computing the OR and AND gates by a probabilistic depth-2 circuit

In [1] it was shown that every set in uniform-AC^0 can be recognized by a uniform family of depth-3 threshold circuits of size n^log^O(1) n. The key step in the proof is simulation of the OR and AND gate on n inputs by a uniform depth-2 probabilistic circuits which consist of one PARITY gate at the root and AND gates on the first level. For every positive constant k, the circuit can be constructed so that its size is n^log^O(1) n, the fan-in of AND gates is O(log^4 n), the number of random inputs is O(log^3 n), and, the error probability is less than 1/n^k. In fact, in [2] the same kind of the circuit was built with the PARITY gate at the root replaced by a MODp gate for any prime p. In this note we generalize the result and show how the simulation can be done with a MODm gate at the root of the circuit, for any integer m ≥ 2. For this we use the idea of randomized polynomials introduced by Tarui [4]. Moreover, our approach gives a slightly simpler argument than the one given in [1] and [2].