When Reduced Connectivity Neural Networks Are Complexity Optimal

Valeriu Beiu

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


    Abstract—The starting points of this paper are two size-optimal solutions: (i) one for implementing arbitrary Boolean functions (Horne, 1994); and (ii) another one for implementing a particular sub-class of Boolean functions (Red’kin, 1970). Because VLSI implementations do not cope well with highly interconnected nets—the area of a chip grows with the cube of the fan-in (Hammerstrom, 1988)—this paper will analyse the influence of limited fan-in on the size optimality for the two solutions mentioned. First, we will extend a result from Horne & Hush (1994) valid for fan-in Δ = 2 to arbitrary fan-in. Second, we will prove that size-optimal solutions are obtained for small constant fan-in for both constructions, while relative minimum size solutions can be obtained for fan-ins strictly lower that linear. These results are in agreement with similar ones proving that for small constant fan-ins (Δ = 6…9) there exist VLSI-optimal (i.e., minimising AT, 2) solutions (Beiu, 1997c), and with the small constants (5…9) relating to our capacity of processing information (Miller, 1956).
    Original languageEnglish
    Title of host publicationInternational Workshop on Neural Networks
    PublisherVU University Press
    Publication statusPublished - Dec 31 1997
    EventHELNET'97 - Montreux, Switzerland
    Duration: Oct 4 1997 → …


    Period10/4/97 → …


    Dive into the research topics of 'When Reduced Connectivity Neural Networks Are Complexity Optimal'. Together they form a unique fingerprint.

    Cite this