Title :
Threshold circuits of bounded depth
Author :
Hajnal, András ; Maass, Wolfgang ; Pudlák, Pavel ; Szegedy, Márló ; Turán, György
Abstract :
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.
Keywords :
Boolean functions; Brain modeling; Circuit simulation; Computational modeling; Computer science; Concurrent computing; Mathematics; Pattern recognition; Polynomials; Statistics;
Conference_Titel :
Foundations of Computer Science, 1987., 28th Annual Symposium on
Conference_Location :
Los Angeles, CA, USA
Print_ISBN :
0-8186-0807-2
DOI :
10.1109/SFCS.1987.59