Most Juntas Saturate the Hardcore Lemma

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^{\mathrm{\prime }}<\text{\hspace{0.17em}⁣}\text{\hspace{0.17em}⁣}<s$. Blanc, Hayderi, Koch, and Tan [FOCS 2024] recently showed that the degradation from $s$ to $s^{\mathrm{\prime }}$ in this lemma is quantitatively tight in certain parameter regimes. We give a simpler and more general proof of this result in almost all parameter regimes of interest by showing that a random junta witnesses the tightness of the hardcore lemma with high probability.