Most Juntas Saturate the Hardcore Lemma

Authors

• Vinayak M. Kumar

Abstract

Consider a function that is mildly hard for size-$s$ circuits. For sufficiently large $s$, Impagliazzo's hardcore lemma guarantees a constant-density subset of inputs on which the same function is extremely hard for circuits of size $s'<\!\!

References