On the tightness of Tiet\"av\"ainen's bound for distributions with limited independence

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\le \frac{n^{1\mathrm{/}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\le \frac{n^{1\mathrm{/}3}}{{\log }^{2}n}$ and for each polynomial $f(v)\in {\mathbb R}[v]$ofdegreeatmost$k$,theexpectedvalueof$f$ with respect to the binomial distribution cannot be positive if $f(w)\le 0$ for each integer $w$ such that $\mathrm{\mid }w-n\mathrm{/}2\mathrm{\mid }\le \sqrt{kn}$. The proof uses tools from approximation theory.