Threshold circuits of bounded depth
András Sándor Hajnal, Wolfgang Maass, Pavel Pudlák, Márió Szegedy, György Turán · 1987
We examine a powerful model of parallel computation: polynomial size threshold circuits of bounded depth (the gates compute threshold functions with polynomial weights). Lower bounds are given to separate polynomial size threshold circuits of depth 2 from polynomial size threshold circuits of depth 3, and from probabilistic polynomial size threshold circuits of depth 2. We also consider circuits of unreliable threshold gates, circuits of imprecise threshold gates and threshold quantifiers.