On the Node Complexity of Threshold Gate Circuits with Sub-linear Fan-ins

This paper discusses size-optimal solutions for implementing arbitrary Boolean functions using threshold gates. After presenting the state-of-the-art, we start from the result of Horne and Hush [12], which shows that threshold gate circuits restricted to fan-in 2 can implement arbitrary Boolean functions, but require O(2 n /n) gates in 2n layers. This result will be generalized to arbitrary fan-ins (Δ), lowering the depth to n/logΔ + n/Δ, and proving that all the (relative) minimums of size are obtained for sub-linear fan-ins (Δ <n − logn). The fact that size-optimal solutions have sub-linear fan-ins is encouraging, as the area and the delay of VLSI implementations are related to the fan-in of the gates.