Most Juntas Saturate the Hardcore Lemma
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914246930989056 |
|---|---|
| author | Kumar, Vinayak M. |
| author_facet | Kumar, Vinayak M. |
| contents | 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'<\!\!<s$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25165 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Most Juntas Saturate the Hardcore Lemma Kumar, Vinayak M. Computational Complexity Data Structures and Algorithms 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'<\!\!<s$. 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. |
| title | Most Juntas Saturate the Hardcore Lemma |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.25165 |