Title: On lower bounds for the depth of threshold circuits with weights from {−1,0,+1}
Abstract: We consider boolean threshold circuits of polynomial size and constant depth. The threshold gates are of unbounded fan-in and with weights from {−1,0, +1}. We introduce the notation of sharp bounded density and prove that boolean functions f n (x) satisfying this property cannot be realized by threshold circuits of depth two with weights from {−1,0,+1}. Furthermore, some properties of threshold circuits are discussed resulting in lower bounds of depth four.
Publication Year: 1995
Publication Date: 1995-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot