Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-032 | 31st May 2000 00:00

On the Computational Power of Winner-Take-All


Publication: 6th June 2000 13:54
Downloads: 5389


In this paper the computational power of a new type of gate is studied:
winner-take-all gates. This work is motivated by the fact that the cost
of implementing a winner-take-all gate in analog VLSI is about the same
as that of implementing a threshold gate.

We show that winner-take-all gates have strictly larger computational
power than threshold gates in the following sense:
a threshold circuit consisting of quadratically many threshold gates is
needed to simulate a single winner-take-all gate.

Furthermore any polysize 2-layer feedforward threshold circuit with
polysize weights can be simulated by a single (!) k-winner-take-all gate
applied to polynomially many linear gates. Hence one arrives here at a
new representation of the second level of the well-known complexity
class TC_0 , which appears to be mathematically more perspicuous.

In the context of computing real valued functions one can show that
arbitrary continuous functions with values in [0,1] can be approximated
on bounded domains by circuits consisting of a single soft winner-take-all
gate applied to linear gates. One may argue that among the known types
of "universal approximators" these circuits are of the simplest mathematical
One just considers a set of linear functions L_1,..,L_n
over the real valued domain, and watches for each argument x the
rank of L_1(x) in the linear order of {L_1(x),...,L_n(x)}.
Up to a fixed scaling of this rank into the target range [0,1],
the "rank" of L_1(x) provides the desired "universal approximator"
that can be used to approximate arbitrary continuous functions.

ISSN 1433-8092 | Imprint