Abstract: The model of local sources captures sources of randomness which are generated by simple processes where each output bit is a function of a small number of uniformly random input bits. Notably, randomness extraction in this model finds applications to randomness extraction from several other classes of sources, such as "bounded-depth" and "small-space" sources, and to the sampling complexity of AC0.
The best known explicit extractors for local sources only work for min-entropy above $\sqrt{n}$, and this is a barrier for current techniques. Towards making progress below this barrier, we characterize the power of random low-degree polynomials as extractors for local sources. Such a characterization also refines structural results of Cohen and Tal (RANDOM 2015) about affine subspaces in solution sets of low-degree polynomials, and has direct implications regarding the AC0 sampling complexity of low-degree polynomials.
As we go along, we will bump into a curious log factor -- trying to understand why it should (or should not) be there will lead us to some combinatorial lemmas that may be of independent interest.
Based on joint work with Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, and Xin Li.