{"ID":2848385,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.25165","arxiv_id":"2510.25165","title":"Most Juntas Saturate the Hardcore Lemma","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'\u003c\\!\\!\u003cs$. Blanc, Hayderi, Koch, and Tan [FOCS 2024] recently showed that the degradation from $s$ to $s'$ 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.","short_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'\u003c\\!\\!\u003cs$. Blanc, Hayderi, Koch, and Tan [FOCS 2024] recently showed that the degrada...","url_abs":"https://arxiv.org/abs/2510.25165","url_pdf":"https://arxiv.org/pdf/2510.25165v2","authors":"[\"Vinayak M. Kumar\"]","published":"2025-10-29T04:49:48Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}