Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-070 | 24th October 2001 00:00

Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing


Authors: Robert Albin Legenstein
Publication: 24th October 2001 11:26
Downloads: 3373


We introduce em total wire length as salient complexity measure
for analyzing the circuit complexity of sensory processing in
biological neural systems and neuromorphic engineering. The 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 exhibit new circuit
design strategies for these benchmark functions that can be
implemented within realistic complexity bounds, in particular with
linear or almost linear total wire length. In addition we derive
general bounds for the total wire length of circuits in terms of
traditional complexity measures.

ISSN 1433-8092 | Imprint