Explicit Two-Source Extractors and Resilient Functions
summary
Constructs an explicit two-source extractor that works for polylogarithmic min-entropy by combining a seeded non-malleable extractor (cycle over seeds to get many almost T‑wise independent bits) with a derandomized Ajtai–Linial style resilient Boolean circuit in monotone AC0. Intermediate string Z has length M with about M^{0.99} bad bits and polylogwise independent good bits; Braverman’s pseudorandomness result lets analysis treat them as uniform, and the extractor yields explicit bipartite Ramsey graphs with K ≈ 2^{poly(log log N)}; construction is explicit and provably correct.
AI-written summary · about
chapters (18)
- 0:00Randomness and weak sources
- 3:56Single-source extraction impossibility
- 5:44Two-source extractors solution
- 8:17History of two-source progress
- 10:47Main result: poly-log min-entropy
- 11:48Applications to Ramsey graphs
- 13:18Construction tools used
- 17:35First attempt: strong seeded extractor
- 18:41Non-malleable extractors second attempt
- 20:58Two-step approach with string Z
- 24:34Second step requirements resilient functions
- 26:20Monotonicity and Braverman's result
- 29:20Ajtai-Linial construction modifications
- 32:10Derandomizing Ajtai-Linial
- 34:05Building partitions from extractors
- 39:29Analysis techniques Jansen's inequality
- 40:39Subsequent work open questions
- 42:22Q&A