Does approximation degree of AND depend on error? Denote $\underline{x}\triangleq x_1,\dots,x_n$.

Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $p_\epsilon(\underline{x})\in\Bbb R[\underline{x}]$ be minimum multilinear multivariate polynomial such that $|p_\epsilon(\underline{x})-f(\underline{x})|\leq\epsilon$ at every $\underline{x}\in\{0,1\}^n$.

Can following strict inequality hold for any boolean function $f$

$$deg(p_\epsilon)&lt;deg(p_{\tilde\epsilon})$$ when $0&lt;\tilde\epsilon&lt;\epsilon&lt;\frac{1}2$?

For example if you consider $AND(x_1,\dots,x_{1000})$, can you actually prove that there is a different approximation degree to approximate $AND(x_1,\dots,x_{1000})$ within error $\frac{1}3$ compared to error $\frac{1}{1000^{1000^{1000^{1000}}}}$?
Firstly it is well-known that the approximate degree of $\mathrm{AND}$ is $O(\sqrt{n})$:

Theorem 1. For all $n$ and $\varepsilon&gt;0$, there exists a multilinear polynomial $p : \{\pm 1\}^n \to \mathbb{R}$ of degree $O(\sqrt{n}\log(1/\varepsilon))$ such that $|p(x)-\mathrm{AND}(x)|\leq \varepsilon$ for all $x \in \{\pm 1\}^n$. 

Proof. We use the Chebyshev polynomials:

Fact. For all $\ell$ and $d$ there exists $p_{\ell,d} : [-1,1] \to \mathbb{R}$ of degree at most $d$ such that $|p_{\ell,d}(z)-z^\ell| \leq 2e^{-d^2/2\ell}$ for all $z \in [-1,1]$.
See Sachdeva-Vishnoi Theorem 3.3 for a proof.

We also have $$\left|\mathrm{AND}(x) - \left(\sum_{i=1}^n \frac{1-x_i}{2n}\right)^\ell\right| \leq \left(1-\frac{1}{n}\right)^\ell \leq e^{-\ell/n}$$ for all $x \in \{\pm 1\}^n$. Thus $$\left|\mathrm{AND}(x) - p_{\ell,d}\left(\sum_{i=1}^n \frac{1-x_i}{2n}\right)\right| \leq 2e^{-d^2/2\ell} + e^{-\ell/n}$$ for all $x \in \{\pm 1\}^n$.

Setting $\ell = n \log(3/\varepsilon)$, $d=\sqrt{2\ell \log(3/\varepsilon)}$, and $p(x) = p_{\ell,d}\left(\sum_{i=1}^n \frac{1-x_i}{2n}\right)$ proves the theorem. Q.E.D.

Now we show that the approximate degree of $\mathrm{AND}$ becomes the exact degree of $\mathrm{AND}$ (which is maximal) for some value of $\varepsilon&gt;0$:

Theorem 2. For all $n$, there exists $\tilde\varepsilon&gt;0$ such that no multilinear polynomial $p : \{\pm 1\}^n \to \mathbb{R}$ of degree strictly less than $n$ satisfies $|p(x) - \mathrm{AND}(x)|\leq \tilde\varepsilon$ for all $x \in \{\pm 1\}^n$.

Proof.
Let $\mathcal{P} \subset \mathbb{R}^{\{\pm 1\}^n}$ be the space of functions from $\{\pm 1\}^n$ to $\mathbb{R}$ that have degree strictly less than $n$.

Claim. $\mathcal{P}$ is closed with respect to the $\ell_\infty$ norm.
This follows from the fact that $\mathcal{P}$ is a linear subspace of $\mathbb{R}^{\{\pm 1\}^n}$. It is spanned by the multilinear monomials of degree strictly less than $n$.

Claim. $\mathrm{AND} \notin \mathcal{P}$.
The Fourier transform uniquely expresses $\mathrm{AND}$ in the multilinear monomial basis. We see that the degree is $n$:
$$\mathrm{AND}(x) = \prod_{i=1}^n \frac{1-x_i}{2} = \sum_{s \subset [n]} \frac{(-1)^{|s|}}{2^n} \prod_{i \in s} x_i.$$

Claim. $\exists \tilde\varepsilon&gt;0~\forall p \in \mathcal{P}~\|\mathrm{AND}-p\|_\infty&gt;\tilde\varepsilon$.
Since $\mathcal{P}$ is closed, its complement is open. $\mathrm{AND}$ is in the complement of $\mathcal{P}$ which means there exists a closed ball of positive radius $\tilde\varepsilon&gt;0$ centered at $\mathrm{AND}$ that does not intersect $\mathcal{P}$.

The final claim is exactly the theorem. 
Q.E.D.

Thus we have shown that there exists $\tilde\varepsilon&gt;0$ such that $\mathrm{deg}_{\tilde\varepsilon}(\mathrm{AND})&gt;\mathrm{deg}_{1/3}(\mathrm{AND})$.