Incompressiblity and Next-Block Pseudoentropy

on YouTube ↗21m

" summary

Shows that a distribution that is k incompressible yields k−2 next‑bit pseudoentropy and that incompressibility is equivalent (up to two bits) to a strong next‑bit pseudoentropy notion. Corollary: t independent copies being tk‑incompressible give next‑bit pseudoentropy roughly k−2/t. For samplable distributions, nontrivial incompressibility implies a one-way function, and conversely no one‑way functions let every samplable distribution be compressed to its entropy+2.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:11Pseudorandomness
3. 1:17Pseudorandom generator
4. 3:53Converting Entropy to Randomness
5. 7:54Computational Analogs of Entropy-cont.
6. 9:30Compression
7. 12:24Recap
8. 17:54Incompressibility⇒ Cryptography

" related talks

• 47mIncompressiblity and Next-Block PseudoentropyIftach Haitner · Minimal Complexity Assumptions for Cryptography 2023
• 31mRandomness Extraction from Somewhat Dependent SourcesOded Goldreich, Marshall Ball, Tal Malkin · ITCS 2022
• 53mFoundations 1Iftach Haitner · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 48mOutput-Compressing Randomized Encodings and ApplicationsHuijia Lin · The Mathematics of Modern Cryptography
• 01h 05mCryptography and Kolmogorov Complexity: A Quick TutorialYanyi Liu · Minimal Complexity Assumptions for Cryptography 2023
• 40mA Duality Between One-Way Functions and Average-Case Symmetry of InformationZhenjian Lu · Lower Bounds, Learning, and Average-Case Complexity
• 36mBounded indistinguishability for simple sourcesYuval Ishai, Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Avi Kaplan, Akshayaram Srinivasan · ITCS 2022
• 01h 17mCrypto + Meta-complexity 2Rafael Pass · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025