Acceptance polynomials and approximate degree on Boolean domains

For a local bit-query algorithm $A$ on $N$ input bits, an acceptance polynomial is a real polynomial $p(X_0,\dots ,X_{N-1})$ such that $p(x)=\mathrm{Pr}[A\text{ accepts }x]$ for every $x\in \{0,1{\}}^N$. The probability is the finite output law of Oracle-only bit-query algorithm.

For a promise function $f:D\to \{0,1\}$ with $D\subseteq \{0,1{\}}^N$ and $ϵ\ge 0$, a polynomial $p$ is an $ϵ$-approximant on $D$ if $\mathrm{\mid }p(x)-f(x)\mathrm{\mid }\le ϵ$ for every $x\in D$. Its total degree is at most $d$ when each monomial with nonzero coefficient has total degree at most $d$. This support convention includes the zero polynomial at every $d\ge 0$, although the formal zero polynomial has no degree (Monomials, coefficients, degree in each variable and total degree in $F[x_1,\dots ,x_n]$).

The $ϵ$-approximate degree ${\stackrel{}{\mathrm{deg}}}_{ϵ}(f;D)$ is the least $d\in {\mathbb{N}}_0$ for which some real polynomial of total degree at most $d$ is an $ϵ$-approximant on $D$. This minimum exists: for $y\in \{0,1{\}}^N$ set ${\delta }_y(X)={\prod }_{i<N}(y_i{X}_i+(1-y_i)(1-X_i))$. For Boolean $x$, each factor is $1$ exactly when $x_i=y_i$ and otherwise is $0$, so ${\delta }_y(x)=1$ exactly for $x=y$. Therefore $p_D(X)={\sum }_{y\in D}f(y){\delta }_y(X)$ equals $f$ on $D$ and has degree at most $N$; if $D=\mathrm{\varnothing }$, the empty sum is zero and is vacuously an approximant. The admissible degree bounds in $\{0,\dots ,N\}$ form a nonempty finite set (it contains $N$), so it has a least element by Every nonempty finite set of reals has a maximum and a minimum applied to its negatives. No choice principle is used.