Complexity bounds on general hard-core predicates. (Q5944107)

A Boolean function is said to be a hard-core predicate for a one-way function if it is efficiently computable, but given the value of the one-way function, the value of the hard-core predicate is difficult to predict. The question studied in the present paper is how hard a function must be in order to be a hard-core predicate. A general condition in terms of Fourier coefficients is given that implies some previous lower bounds (e.g., hard-core predicates cannot be in \(\text{ AC}^0\)) as well as some interesting new lower bounds (in terms of monotone circuits and threshold circuits).