# 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)<deg(p_{\tilde\epsilon})$$ when $0<\tilde\epsilon<\epsilon<\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}}}}$?

• Yes. AND can be approximated with degree $O(\sqrt{n})$ with error $\epsilon=1/3$. However, the exact degree of AND is $n$, which means that the approximate degree is $n$ for some $\tilde\epsilon>0$. (This follows from the fact that the space of bounded degree $<n$ polynomials is compact.) – Thomas Jun 4 '15 at 5:09
• You have edited this question 16 times in under a week. I am hoping that you are not doing so to bump up your question (which would be an abuse of the edit functionality). Please spend more time thinking before posting/editing and keep your number of edits to minimal required. – Kaveh Jun 4 '15 at 5:51
• no not bumping. I am really looking for an example. I thought may be AND might work here. – 1.. Jun 4 '15 at 9:15
• @Thomas "However, the exact degree of AND is n, which means that the approximate degree is n for some ϵ~>0. (This follows from the fact that the space of bounded degree <n polynomials is compact.)" this is not clear. You are claiming but not proving. – 1.. Jun 4 '15 at 9:15
• You are claiming that somehow from compactness degree separation happens but not proving anything rigorously. – 1.. Jun 4 '15 at 9:48

Firstly it is well-known that the approximate degree of $\mathrm{AND}$ is $O(\sqrt{n})$:

Theorem 1. For all $n$ and $\varepsilon>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>0$:

Theorem 2. For all $n$, there exists $\tilde\varepsilon>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>0~\forall p \in \mathcal{P}~\|\mathrm{AND}-p\|_\infty>\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>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>0$ such that $\mathrm{deg}_{\tilde\varepsilon}(\mathrm{AND})>\mathrm{deg}_{1/3}(\mathrm{AND})$.

• Looks like a pretty good answer. Let me check carefully. – 1.. Jun 4 '15 at 17:30
• Pretty good answer. Let me ask you one more question. You say that there exists $\epsilon<1/2$ such that $deg_{1/3}(AND)>deg_{\epsilon}(f)$. This is pretty solid founded in your proof here. Take $\epsilon$ to be greatest such that $\deg_\epsilon=deg(AND)=n$. Can we prove $\exists\eta_1,\eta_2$ with $0<\epsilon<\eta_1<\eta_2<1/2$, such that $deg_{\eta_1}(AND)\neq deg_{\eta_2}(AND)$? Is there really a grading of degrees with change in error of approximation? – 1.. Jun 4 '15 at 17:41
• I may be missing something, but I don't think this proof shows that theorem 2 is true for $\tilde{\varepsilon}$ independent of $n$? – Sasho Nikolov Jun 4 '15 at 19:11
• I do not think $\tilde{\epsilon}$ cannot be independent of $n$ (I suppose this is the degree). I think there is an implicit dependence of $\tilde{\epsilon}$ on degree. I also seem to think that his answer can be bootstrapped to give a grading. Only thing this answer does not seem to state is what is the step level of degree in grading. I think that is beyond the techniques of this answer. – 1.. Jun 4 '15 at 19:14
• Sorry, yes, you are absolutely right: by theorem 1, the degree is $o(n)$ as long as $\epsilon = 2^{-o(\sqrt{n})}$. – Sasho Nikolov Jun 4 '15 at 19:17

I believe the $\epsilon$-approximate degree of AND is known (up to constants) and is

$\text{deg}_{\epsilon}(\text{AND}_n)= \Theta(\sqrt{n\log(1/\epsilon)})$.

Indeed, the degree gets higher as you demand better approximations, eventually reaching $\Omega(n)$ once you want exponentially small error.

This result has probably been reproved many times in the literature. One paper that proves both the upper and lower bound is the following:

R. de Wolf. A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions. In Quantum Information and Computation, 8(10):943-950, 2008. quant-ph/0802.1816