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

Valeriu Beiu

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.
    Original languageEnglish
    Title of host publicationInternational Conference on Neural Networks and Soft Computing
    ISBN (Print)978-3-7908-0005-0
    Publication statusPublished - 2003
    EventICNNSC'02 - Zakopane, Poland
    Duration: Jun 11 2002 → …


    Period6/11/02 → …


    Dive into the research topics of 'On the Node Complexity of Threshold Gate Circuits with Sub-linear Fan-ins'. Together they form a unique fingerprint.

    Cite this