Neural Computation with Winner-Take-All as the Only Nonlinear Operation

Everybody "knows" that neural networks need more than a single layer ofnonlinear units to compute interesting functions. We show that this is false if one employs winner-take-all as nonlinear unit: - Any boolean function can be computed by a single k-winner-takeall unitapplied to weighted sums of the input variables.