The Wire-Length Complexity of Neural Networks

R. A. Legenstein


The ability of our nervous system to rapidly process and react on the huge amount of sensory input data is grounded on its massively parallel architecture. Arguably, physical cost for communication, that is to say the space needed for wires, is the most severe bottleneck in biological as well as in artificial architectures of this type. In this thesis the complexity of wiring in biological and artificial neural networks, the implications of wiring constraints to models for brain circuits, and the implementation of wire-efficient circuit designs in hardware are studied. We present a simple mathematical framework that allows us to study the wiring complexity of neural circuits in a formal and general manner. In this model, the complexity of a circuit is measured by the total length of wires needed to implement the circuit, a complexity measure that is one of the most salient ones if real-world constraints of implementations in hardware or ``wetware'' are considered.Furthermore, we study the layout of general computational structures like tree computations. We give tight upper and lower bounds on the wire length of constrained tree layouts and show efficient layout strategies for prefix computations.

Reference: R. A. Legenstein. The Wire-Length Complexity of Neural Networks. PhD thesis, Graz University of Technology, 2002.