  We continue a line of work on extracting random bits from weak sources that
are generated by simple processes. We focus on the model of locally samplable
sources, where each bit in the source depends on a small number of (hidden)
uniformly random input bits. Also known as local sources, this model was
introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely
related to sources generated by $\mathsf{AC}^0$ circuits and bounded-width
branching programs. In particular, extractors for local sources also work for
sources generated by these classical computational models.
  Despite being introduced a decade ago, little progress has been made on
improving the entropy requirement for extracting from local sources. The
current best explicit extractors require entropy $n^{1/2}$, and follow via a
reduction to affine extractors. To start, we prove a barrier showing that one
cannot hope to improve this entropy requirement via a black-box reduction of
this form. In particular, new techniques are needed.
  In our main result, we seek to answer whether low-degree polynomials (over
$\mathbb{F}_2$) hold potential for breaking this barrier. We answer this
question in the positive, and fully characterize the power of low-degree
polynomials as extractors for local sources. More precisely, we show that a
random degree $r$ polynomial is a low-error extractor for $n$-bit local sources
with min-entropy $\Omega(r(n\log n)^{1/r})$, and we show that this is tight.
  Our result leverages several new ingredients, which may be of independent
interest. Our existential result relies on a new reduction from local sources
to a more structured family, known as local non-oblivious bit-fixing sources.
To show its tightness, we prove a "local version" of a structural result by
Cohen and Tal (RANDOM 2015), which relies on a new "low-weight"
Chevalley-Warning theorem.
