  The $\epsilon$-approximate degree $deg_\epsilon(f)$ of a Boolean function $f$
is the least degree of a real-valued polynomial that approximates $f$ pointwise
to error $\epsilon$. The approximate degree of $f$ is at least $k$ iff there
exists a pair of probability distributions, also known as a dual polynomial,
that are perfectly $k$-wise indistinguishable, but are distinguishable by $f$
with advantage $1 - \epsilon$. Our contributions are:
  We give a simple new construction of a dual polynomial for the AND function,
certifying that $deg_\epsilon(f) \geq \Omega(\sqrt{n \log 1/\epsilon})$. This
construction is the first to extend to the notion of weighted degree, and
yields the first explicit certificate that the $1/3$-approximate degree of any
read-once DNF is $\Omega(\sqrt{n})$.
  We show that any pair of symmetric distributions on $n$-bit strings that are
perfectly $k$-wise indistinguishable are also statistically $K$-wise
indistinguishable with error at most $K^{3/2} \cdot \exp(-\Omega(k^2/K))$ for
all $k < K < n/64$. This implies that any symmetric function $f$ is a
reconstruction function with constant advantage for a ramp secret sharing
scheme that is secure against size-$K$ coalitions with statistical error
$K^{3/2} \exp(-\Omega(deg_{1/3}(f)^2/K))$ for all values of $K$ up to $n/64$
simultaneously. Previous secret sharing schemes required that $K$ be determined
in advance, and only worked for $f=$ AND.
  Our analyses draw new connections between approximate degree and
concentration phenomena.
  As a corollary, we show that for any $d < n/64$, any degree $d$ polynomial
approximating a symmetric function $f$ to error $1/3$ must have $\ell_1$-norm
at least $K^{-3/2} \exp({\Omega(deg_{1/3}(f)^2/d)})$, which we also show to be
tight for any $d > deg_{1/3}(f)$. These upper and lower bounds were also
previously only known in the case $f=$ AND.
