  We explicitly construct the first nontrivial extractors for degree $d \ge 2$
polynomial sources over $\mathbb{F}_2^n$. Our extractor requires min-entropy
$k\geq n - \tilde{\Omega}(\sqrt{\log n})$. Previously, no constructions were
known, even for min-entropy $k\geq n-1$. A key ingredient in our construction
is an input reduction lemma, which allows us to assume that any polynomial
source with min-entropy $k$ can be generated by $O(k)$ uniformly random bits.
  We also provide strong formal evidence that polynomial sources are unusually
challenging to extract from, by showing that even our most powerful general
purpose extractors cannot handle polynomial sources with min-entropy below
$k\geq n-o(n)$. In more detail, we show that sumset extractors cannot even
disperse from degree $2$ polynomial sources with min-entropy $k\geq
n-O(n/\log\log n)$. In fact, this impossibility result even holds for a more
specialized family of sources that we introduce, called polynomial
non-oblivious bit-fixing (NOBF) sources. Polynomial NOBF sources are a natural
new family of algebraic sources that lie at the intersection of polynomial and
variety sources, and thus our impossibility result applies to both of these
classical settings. This is especially surprising, since we do have variety
extractors that slightly beat this barrier - implying that sumset extractors
are not a panacea in the world of seedless extraction.
