Lower bound of degree of polynomial approximating parity

Question

Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$

It is known [See e.g. Lemma 5 of this lecture note] that any polynomial $f(x_1,\dots,x_n) \in \mathbb{R}[x_1,\dots,x_n]$ of degree at most $\sqrt{n}$ must disagree with $\text{MOD}_2$ on at least a constant fraction of inputs.

Is this true for a polynomial with degree $n^{0.5+\epsilon}$ for some small constant $\epsilon>0$ ? How about a polynomial with degree $o(n)$?

Answer 1

You can show a polynomial of degree $O(\sqrt{n\log n})$ can agree with parity on all but $o(1)$ fraction of the inputs. (In fact, this argument should work for anything of degree $\omega(\sqrt{n})$).

Let $S = x_1 + x_2 + \dots + x_n$. Note that $\text{MOD}_2(x_1, x_2, \dots, x_n)$ can be written as a single-variable function of $S$. By Lagrange interpolation, there exists a univariate polynomial of degree $O(\sqrt{n\log n})$ in $S$ (and hence in the $x_i$s) that agrees with $\text{MOD}_2$ on the interval $S \in [(n-\sqrt{n\log n})/2, (n+\sqrt{n\log n})/2]$. By the central limit theorem, this range of $S$ accounts for all but $o(1)$ of the $2^n$ inputs $(x_1, x_2, \dots, x_n)$.