Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Low-error two-source extractors

Probability

Speaker: Jesse Goodman, Simons Institute
Location: 2112 MSB
Start time: Thu, Nov 5 2026, 1:10PM

Description

We give the first explicit construction of low-error two-source extractors for min-entropy k = o(n). Our construction is based on a new regularity lemma for low-rank matrices, which provides the first polynomial bounds for the approximate duality conjecture. The key ingredient is a new result on rapid mixing in F2^n, which shows that every spread set enjoys iterative sum-product type growth, under addition alone. Along the way, we explicitly construct new low-error affine extractors, and more. Joint work with Dean Doron.