On Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
summary
Asks whether scaling the Impagliazzo–Wigderson assumption yields an extreme high-end PRG (seed R = (1+o(1))·L, output M ≈ 2^{1−o(1)·L}, total compute ≈ 2^{2+o(1)·L}, giving deterministic simulation exponent C≈2). Shows every black‑box construction map must be an extractor yet differ from a typical extractor (there exists a high‑entropy source on which many outputs of E are fixed). Rules out the pseudo-entropy generator plus extractor route (seed X cannot be o(L)). Rules out composing PRGs when using hardness amplification plus the hybrid argument.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:11Summary and Outline
- 2:57Hardness vs. Randomness state of the art
- 12:27The cost of the hybrid argument
- 16:27Black-box proofs for showing extreme high-end IW hardness assumption = extreme high-en
- 20:38Our results: Limitations on some approaches fa "extreme black-box proof"
- 29:26The "PEG + Extractor" approach of [DMOZ20] can't yield an extreme bb-proof.
- 35:13The "PRG composition" approach of CT21 can't give an extreme bb-proof using Hardness Amplification + Hybrid Argument
- 42:27Conclusion and Open Problems
