Inform. Process. Lett., 2012, Volume 112, Issue 7, Pages 267–271
Exponential lower bound for bounded depth circuits with few threshold gates
V. V. Podolskii
Steklov Mathematical Institute, Gubkina str. 8, 119991, Moscow, Russia
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.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|