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.
