## Abstract

We consider the class Σ_{3}^{k} 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(n^{1/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 NC^{1} that requires 2^{n-o(n)} size depth 3 circuits. The main tool is a theorem that shows that any Σ_{3}^{2} 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 x_{i} = 0, x_{i} = 1, x_{i} = x_{j} or x_{i} = x̄_{j}) of dimension at least log(a/s)/log n.

Original language | English (US) |
---|---|

Pages (from-to) | 86-91 |

Number of pages | 6 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - 1997 |

Externally published | Yes |

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

- Software