Semi-unbounded fan-in circuits: Boolean vs. arithmetic
Anna Gál · 2002
We prove that polynomial size semi-unbounded fan-in Boolean circuits of depth d can be simulated by polynomial size semi-unbounded fan-in arithmetic circuits of depth O(d+log n), where the arithmetic operations +, -, /spl times/ are performed in an arbitrary finite field. It is impossible to achieve this via gate-by-gate simulation. Instead, the proof is based on a randomized reduction to "unique witnesses" in the spirit of L.G. Valiant and V.V. Vazirani (1986) K. Mulmuley et al. (1987) and A. Wigderson (1994).