Wire Length as a Circuit Complexity Measure
R. A. Legenstein and W. Maass
We introduce wire length as a salient complexity measure for analyzing
the circuit complexity of sensory processing in biological neural systems.
This new complexity measure is applied in this paper to two basic
computational problems that arise in translation- and scale-invariant pattern
recognition, and hence appear to be useful as benchmark problems for sensory
processing. We present new circuit design strategies for these benchmark
problems that can be implemented within realistic complexity bounds, in
particular with linear or almost linear wire length. Finally we derive some
general bounds which provide information about the relationship between new
complexity measure wire length and traditional circuit complexity measures.
Reference: R. A. Legenstein and W. Maass.
Wire length as a circuit complexity measure.
Journal of Computer and System Sciences, 70:53-72, 2005.