RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB

 Inform. Process. Lett., 2012, Volume 112, Issue 7, Pages 267–271 (Mi ipl1)

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.

DOI: https://doi.org/10.1016/j.ipl.2011.12.011

Bibliographic databases:

Revised: 07.12.2011
Accepted:09.12.2011
Language: