  In 1990, Tiet\"av\"ainen showed that if the only information we know about a
linear code is its dual distance $d$, then its covering radius $R$ is at most
$\frac{n}{2}-(\frac{1}{2}-o(1))\sqrt{dn}$. While Tiet\"av\"ainen's bound was
later improved for large values of $d$, it is still the best known upper bound
for small values including the $d = o(n)$ regime. Tiet\"av\"ainen's bound holds
also for $(d-1)$-wise independent probability distributions on $\{0,1\}^n$, of
which linear codes with dual distance $d$ are special cases. We show that
Tiet\"av\"ainen's bound on $R-\frac{n}{2}$ is asymptotically tight up to a
factor of $2$ for $k$-wise independent distributions if
$k\leq\frac{n^{1/3}}{\log^2{n}}$. Namely, we show that there exists a $k$-wise
independent probability distribution $\mu$ on $\{0,1\}^n$ whose covering radius
is at least $\frac{n}{2}-\sqrt{kn}$. Our key technical contribution is the
following lemma on low degree polynomials, which implies the existence of $\mu$
by linear programming duality. We show that, for sufficiently large
$k\leq\frac{n^{1/3}}{\log^2{n}}$ and for each polynomial $f(v)\in {\mathbb
R}[v]$ of degree at most $k$, the expected value of $f$ with respect to the
binomial distribution cannot be positive if $f(w)\leq 0$ for each integer $w$
such that $|w-n/2|\leq\sqrt{kn}$. The proof uses tools from approximation
theory.
