Title

Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1985

Abstract

Let = {f1, f2,…} be a family of symmetric Boolean functions, where fn has n Boolean variables, for each n⩾ 1. Let μ(n) be the minimum number of variables of fn 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.