On the tightness of Tietäväinen's bound for distributions with limited independence

Abstract

In 1990, Tietäväinen 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äväinen'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äväinen'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äväinen'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/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/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)\le 0$ for each integer $w$ such that $|w-n/2|\le \sqrt{kn}$. The proof uses tools from approximation theory.