Paper Info
Title
Threshold circuits of bounded depth
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 circuits of depth 2. With regard to the unreliability of bounded depth circuits, it is shown that the class of functions computed reliably with bounded depth circuits of unreliable ∨, ∧, ¬ gates is narrow. On the other hand, functions computable by bounded depth, polynomial-size threshold circuits can also be computed by such circuits of unreliable threshold gates. Furthermore we examine to what extent imprecise threshold gates (which behave unpredictably near the threshold value) can compute nontrivial functions in bounded depth and a bound is given for the permissible amount of imprecision. We also discuss threshold quantifiers and prove an undefinability result for graph connectivity.
Year
DOI
Venue
1993
10.1016/0022-0000(93)90001-D
FOCS
Keywords
Field
DocType
threshold circuit,bounded depth,sorting,logic gates,polynomials,computer science,automata,machine learning,computational modeling,random variables,boolean functions,concurrent computing,error correction,lower bound,pattern recognition,parallel computer,mathematics,statistics,reliability
Boolean function,Discrete mathematics,Random variable,Logic gate,Combinatorics,Polynomial,Computer science,Error detection and correction,Probabilistic logic,Electronic circuit,Bounded function
Journal
Volume
Issue
ISSN
46
2
Journal of Computer and System Sciences
Citations 
PageRank 
References 
146
9.90
14
Authors
5
Search Limit
100146
Name
Order
Citations
PageRank
András Hajnal120824.43
Wolfgang Maass23717391.51
Pavel Pudlák31378134.50
György Turán462680.88
Márió Szegedy515010.28