Randomness Extraction from Somewhat Dependent Sources

on YouTube ↗31m

" summary

Defines three dependence models and gives sharp positive and negative results: T-coordinated sources admit deterministic extraction — any two‑source extractor for independent sources with min‑entropy K yields a 2ε extractor for T‑coordinated sources with min‑entropy K+T+log(1/ε), and this K+T+log loss is optimal. The other models (bounded cross‑influence and bounded mutual information) resist extraction but admit condensation: cross‑influence condensers incur a 2^T error blowup and +T deficiency, and those parameters are essentially tight. Also shows sampling inner‑product needs ≥0.49N bits.

AI-written summary · about

" chapters (12)

1. 0:00Introduction
2. 2:05Natural sources of randomness
3. 3:23Seeded extractors
4. 5:50Background
5. 7:05Models
6. 9:35TCoordinated Sources
7. 12:13TCross Influence
8. 15:37Mutual Information
9. 16:54Relation Between Models
10. 18:54Extractors and Condensers
11. 20:39Condensers
12. 23:13Theorem

" related talks

• 21mIncompressiblity and Next-Block PseudoentropyIftach Haitner, Noam Mazor, Jad Silbak · ITCS 2023
• 47mIncompressiblity and Next-Block PseudoentropyIftach Haitner · Minimal Complexity Assumptions for Cryptography 2023
• 31mCryptographic Hardness of Correlated SamplingRussell Impagliazzo · Minimal Complexity Assumptions for Cryptography 2023
• 47mHardness of LWE on General Entropic DistributionsNico Döttling · Lattices: New Cryptographic Capabilities 2020
• 48mOutput-Compressing Randomized Encodings and ApplicationsHuijia Lin · The Mathematics of Modern Cryptography
• 41mReducibility and Statistical-Computational Gaps from Secret LeakageGuy Bresler · Computational Phase Transitions (Simons Institute, 2020)
• 01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other TopicsAllison Bishop · The Mathematics of Modern Cryptography
• 40mOn the Complexity of Two-Party Differential PrivacyNaom Mazor · Minimal Complexity Assumptions for Cryptography 2023