Depth-2 Threshold Circuits: Provable Limitations
Circuits with linear threshold functions as primitives are a natural model for computation in the brain. Small threshold circuits of depth two cannot compute most functions, but how do we prove such a statement? And how do we lay our hands on explicit functions that they cannot compute? This article gives an overview of the landscape.
Volume 28 | Issue 9