Low-Degree Polynomials Are Good Extractors

In this talk we will discuss the bias of random multivariate low-degree polynomials over F_2. Previous work has shown that random low-degree polynomials are, with high probability, unbiased on a uniformly random input.

We will consider more general notions of "bias" for low-degree polynomials. In particular, we will see that most low-degree polynomials are good extractors for all sufficiently small families of sources, and also for sumset sources, which are the most general large family of sources we know.

These results imply new complexity separations for linear ROBPs. The two main tools we use are a new structural result on sumset-punctured Reed-Muller codes, paired with a novel type of reduction between extractors. Using the new structural result, we obtain new limits on the power of sumset extractors, strengthening and generalizing the impossibility results of Chattopadhyay, Goodman, and Gurumukhani (ITCS 2024).

This talk is based on joint work with Omar Alrabiah, Jesse Goodman, and Jonathan Mosheiff.