Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions

Authors

Ronald Fagin, IBM Research Laboratory
Maria M. Klawe, IBM Research Laboratory
Nicholas Pippenger, Harvey Mudd CollegeFollow
Larry Stockmeyer, IBM Research Laboratory

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1985

Abstract

Let = {f₁, f₂,…} be a family of symmetric Boolean functions, where f_n has n Boolean variables, for each n⩾ 1. Let μ(n) be the minimum number of variables of f_n that each have to be set to constant values so that the resulting function is a constant function. We show that the growth rate of μ(n) completely determines whether or not the family is ‘good’, that is, can be realized by a family of constant-depth, polynomial-size circuits (with unbounded fan-in). Furthermore, if μ(n) ⩽ (log n)^k for some k, then the family is good. However, if μ(n) ⩾ n^ϵ for some ϵ > 0, then the family is not good.

Rights Information

© 1985 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/0304-3975(85)90045-3

Recommended Citation

Ronald Fagin, Maria M. Klawe, Nicholas J. Pippenger, Larry Stockmeyer, Bounded-depth, polynomial-size circuits for symmetric functions, Theoretical Computer Science, Volume 36, 1985, Pages 239-250, ISSN 0304-3975, 10.1016/0304-3975(85)90045-3. (http://www.sciencedirect.com/science/article/pii/0304397585900453)