|
This article is cited in 3 scientific papers (total in 3 papers)
Exponential lower bound for bounded depth circuits with few threshold gates
V. V. Podolskii Steklov Mathematical Institute, Gubkina str. 8, 119991, Moscow, Russia
Abstract:
We prove an exponential lower bound on the size of bounded depth circuits with $O(\log n)$
threshold gates computing an explicit function (namely, the parity function).
Previously exponential lower bounds were known only for circuits with one threshold gate.
Superpolynomial lower bounds are known for circuits with $O(\log n)$ threshold gates.
Received: 26.05.2011 Revised: 07.12.2011 Accepted: 09.12.2011
Linking options:
https://www.mathnet.ru/eng/ipl1
|
|