We consider the class Σ3k of unbounded fan-in depth-3 boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has Ω(2εn/k) gates (for k = O(n1/2)) for some ε>0, and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC1 that requires 2n-o(n) size depth 3 circuits. The main tool is a theorem that shows that any Σ32 circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form xi = 0, xi = 1, xi = xj or xi = x̄j) of dimension at least log(a/s)/log n.
|Original language||English (US)|
|Number of pages||6|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1997|
|Event||Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA|
Duration: May 4 1997 → May 6 1997
All Science Journal Classification (ASJC) codes