DocumentCode :
2185897
Title :
Threshold circuits of bounded depth
Author :
Hajnal, András ; Maass, Wolfgang ; Pudlák, Pavel ; Szegedy, Márló ; Turán, György
fYear :
1987
fDate :
12-14 Oct. 1987
Firstpage :
99
Lastpage :
110
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1987., 28th Annual Symposium on
Conference_Location :
Los Angeles, CA, USA
ISSN :
0272-5428
Print_ISBN :
0-8186-0807-2
Type :
conf
DOI :
10.1109/SFCS.1987.59
Filename :
4568260
Link To Document :
بازگشت