Complexity bounds on general hard-core predicates

A Boolean function b is a hard-core predicate for a one-way function S if b is polynomial-time computable but b(x) is difficult to predict from lf(x). A general one-way function. A seminal result of Goldreich and Levin assert s that the family of parity functions is a general family of hard-core pred icates. We show that no general family of hard-core predicates can consist of functions with O(n(1-epsilon)) average sensitivity for any epsilon > 0. As a result, such families cannot consist of functions in AC(0), monotone functions, functions computed by generalized threshold gates, or symmetric d-threshold functions, for d = O(n(1/2-epsilon)) and epsilon > 0.