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 provides a subset of inputs on which the same function is extremely hard for circuits of size \(s' \ll s\). Blanc, Hayderi, Koch, and Tan [FOCS, 2024] proved that the size degradation from \(s\) to \(s'\) present in this lemma is quantitatively tight. We give a much simpler proof of this fact by showing that the hardcore lemma is tight for a random junta with high probability.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Quantum Computing Algorithms and Architecture
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 142–150
- Publication date
- 1 January 2026
- Language
- EN