On the computational power of winner-take-all

This article initiates a rigorous theoretical analysis of the computational power of circuits that employ modules for computing winner-take-all. Compu tational models that involve competitive stages have so far been neglected in computational complexity theory, although they are widely used in comput ational brain models, artificial neural networks, and analog VLSI. Our theo retical analysis shows that winner-take-all is a surprisingly powerful comp utational module in comparison with threshold gates (also referred to as Mc Culloch-Pitts neurons) and sigmoidal gates. We prove an optimal quadratic l ower bound for computing winner-take-all in any feedforward circuit consist ing of threshold gates. In addition we show that arbitrary continuous funct ions can be approximated by circuits employing a single soft winner-take-al l gate as their only nonlinear operation. Our theoretical analysis also provides answers to two basic questions raise d by neurophysiologists in view of the well-known asymmetry between excitat ory and inhibitory connections in cortical circuits: how much computational power of neural networks is lost if only positive weights are employed in weighted sums and how much adaptive capability is lost if only the positive weights are subject to plasticity.