An Algebraic Model for Bounding Threshold Circuit Depth

Abstract

We define a new structured and general model of computation: circuits using arbitrary fan- in arithmetic gates over the characteristic two finite fields (F_2n). These circuits have only one input and one output. We show how they correspond naturally to boolean computations with n inputs and n outputs. We show that if circuit sizes are polynomially related then the arithmetic circuit depth and the threshold circuit depth to compute a given function differ by at most a constant factor. We use threshold circuits that allow arbitrary integer weights; however, we show that when compared to the usual threshold model, the depth measure of this generalised model only differs by at most a constant factor (at polynomial size). The fan-in of our arithmetic model is also unbounded in the most generous sense: circuit size is measured as the number of Sum and ½ gates; there is no bound on the number of ''wires'' . We show that these results are provable for any ''reasonable'' correspondance between bit strings of n-bits and elements of F_ 2n. And, we find two distinct characterizations of ''reasonable''. Thus, we have shown that arbitrary fan-in arithmetic computations over F_ 2n constitute a precise abstraction of boolean threshold computations with the pleasant property that various algebraic laws have been recovered.