On the Complexity of Hard-Core Set Constructions

We study a fundamental result of Impagliazzo (

FOCS’95

) known as the hard-core set lemma. Consider any function

f

:{0,1}

n

→{0,1} which is “mildly-hard”, in the sense that any circuit of size

s

must disagree with

f

on at least

δ

fraction of inputs. Then the hard-core set lemma says that

f

must have a hard-core set

H

of density

δ

on which it is “extremely hard”, in the sense that any circuit of size

s’=

$ {O} {(s/({{1}\over{\varepsilon^2}}\log(\frac{1}{\varepsilon\delta})))}$

must disagree with

f

on at least (1 − 

ε

)/2 fraction of inputs from

H

.

There are three issues of the lemma which we would like to address: the loss of circuit size, the need of non-uniformity, and its inapplicability to a low-level complexity class. We introduce two models of hard-core set constructions, a strongly black-box one and a weakly black-box one, and show that those issues are unavoidable in such models.

First, we show that in any strongly black-box construction, one can only prove the hardness of a hard-core set for smaller circuits of size at most

$s'=O(s/(\frac{1}{\varepsilon^2}log\frac{1}{\delta}))$

. Next, we show that any weakly black-box construction must be inherently non-uniform — to have a hard-core set for a class

G

of functions, we need to start from the assumption that

f

is hard against a non-uniform complexity class with

$\Omega(\frac{1}{\varepsilon}log|G|)$

bits of advice. Finally, we show that weakly black-box constructions in general cannot be realized in a low-level complexity class such as

AC

0

[

p

] — the assumption that

f

is hard for

AC

0

[

p

] is not sufficient to guarantee the existence of a hard-core set.