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

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

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

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

<blockquote>
  <p>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 </p>
</blockquote>

CC BY-SA 3.0
2015-06-09T21:02:30.290Z
2015-06-09T21:02:30.290Z
Robin Kothari
<p>Firstly it is well-known that the approximate degree of $\mathrm{AND}$ is $O(\sqrt{n})$:</p>

<p><b>Theorem 1.</b> 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$. </p>

<p><i>Proof.</i> We use the Chebyshev polynomials:</p>

<p><b>Fact.</b> 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]$.<br>
See <a href="http://research.microsoft.com/en-us/um/people/nvishno/site/Publications_files/approx-survey.pdf" rel="nofollow">Sachdeva-Vishnoi</a> Theorem 3.3 for a proof.</p>

<p>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$.</p>

<p>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.</p>

<p>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$:</p>

<p><b>Theorem 2.</b> 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$.</p>

<p><i>Proof.</i>
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$.</p>

<p><b>Claim.</b> $\mathcal{P}$ is closed with respect to the $\ell_\infty$ norm.<br>
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$.</p>

<p><b>Claim.</b> $\mathrm{AND} \notin \mathcal{P}$.<br>
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.$$</p>

<p><b>Claim.</b> $\exists \tilde\varepsilon&gt;0~\forall p \in \mathcal{P}~\|\mathrm{AND}-p\|_\infty&gt;\tilde\varepsilon$.<br>
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}$.</p>

<p>The final claim is exactly the theorem. 
Q.E.D.</p>

<p>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})$.</p>

CC BY-SA 3.0
2015-06-04T17:30:55.967Z
Looks like a pretty good answer. Let me check carefully.
Turbo
CC BY-SA 3.0
2015-06-04T17:41:18.013Z
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?
Turbo
CC BY-SA 3.0
2015-06-04T19:11:00.967Z
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
CC BY-SA 3.0
2015-06-04T19:14:43.113Z
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.
Turbo
CC BY-SA 3.0
2015-06-04T19:17:11.430Z
Sorry, yes, you are absolutely right: by theorem 1, the degree is $o(n)$ as long as $\epsilon = 2^{-o(\sqrt{n})}$.
Sasho Nikolov
CC BY-SA 3.0
2015-06-04T19:19:55.233Z
BTW is this only for AND function?? or can this be adapted to any boolean function of degree n?
Turbo
CC BY-SA 3.0
2015-06-04T22:48:22.103Z
@Thomas This technique seems to work for all functions of given degree. Also do you know what the minimum gap $1/2-\eta$ is from case $\deg_{1/2}(f)=0$ to $deg_\eta(f)>0$ in terms of real degree $\deg_{0}(f)$ for general boolean function $f$ in $n$ variables. Is this $1/d$?
Turbo
CC BY-SA 3.0
2015-06-05T01:13:46.473Z
Theorem 2 also works for parity function when we move from $e=1/2$ to $e<1/2$ (reverse of case considered here where we go from $e=0$ to $e>0$). However we know approximation degree is $\Omega(n)$ for all $e<1/2$? Your proof also works at corner case of $e=1/2$ where parity has degree $0$. However degree of $e<1/2$ is $\Omega(n)$. That is there is no open interval here.
Turbo
CC BY-SA 3.0
2015-06-04T16:29:16.503Z
2015-06-06T20:48:02.453Z
2015-06-06T20:48:02.453Z
Thomas Steinke
<p>Denote $\underline{x}\triangleq x_1,\dots,x_n$.</p>

<p>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$.</p>

<p>Can following strict inequality hold for any boolean function $f$</p>

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

<p>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}}}}$?</p>

CC BY-SA 3.0
2015-06-04T05:09:56.050Z
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 Steinke
CC BY-SA 3.0
2015-06-04T05:51:06.537Z
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
CC BY-SA 3.0
2015-06-04T09:15:00.823Z
no not bumping. I am really looking for an example. I thought may be AND might work here.
Turbo
CC BY-SA 3.0
2015-06-04T09:15:43.537Z
@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.
Turbo
CC BY-SA 3.0
2015-06-04T09:48:05.717Z
You are claiming that somehow from compactness degree separation happens but not proving anything rigorously.
Turbo
CC BY-SA 3.0
2015-06-04T16:29:37.073Z
I elaborated my comment into an answer.
Thomas Steinke
CC BY-SA 3.0
2015-06-04T18:42:53.227Z
To add to @Kaveh's comment, the question seems to have changed substantially since it was first posted (I may be wrong). I don't think it's a good idea to post one question and edit it to make it something quite different.
Sasho Nikolov
CC BY-SA 3.0
2015-06-04T19:06:15.027Z
@SashoNikolov Thank you for your comment. You are right that I did not make the question specific (the question remains essentially the same though).
Turbo
<boolean-functions><polynomials>
Does approximation degree of AND depend on error?
Turbo
# Does approximation degree of AND depend on error?

(Asked by: username_0 on 2015-05-30)

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)

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}}}}$?

**Tags:** boolean-functions, polynomials

> **Comments:**
> **username_1**: 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.)  
> **username_2**: 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.  
> **username_0**: no not bumping. I am really looking for an example. I thought may be AND might work here.  
> **username_0**: @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.  
> **username_0**: You are claiming that somehow from compactness degree separation happens but not proving anything rigorously.  
> **username_1**: I elaborated my comment into an answer.  
> **username_3**: To add to @username_2's comment, the question seems to have changed substantially since it was first posted (I may be wrong). I don't think it's a good idea to post one question and edit it to make it something quite different.  
> **username_0**: @SashoNikolov Thank you for your comment. You are right that I did not make the question specific (the question remains essentially the same though).  

---

## 2 answers

### Answer by username_4 on 2015-06-09. Score: 6

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


---

### Answer by username_1 on 2015-06-04. Score: 6

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](http://research.microsoft.com/en-us/um/people/nvishno/site/Publications_files/approx-survey.pdf) 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})$.

> **Comments:**
> **username_0**: Looks like a pretty good answer. Let me check carefully.  
> **username_0**: 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?  
> **username_3**: I may be missing something, but I don't think this proof shows that theorem 2 is true for $\tilde{\varepsilon}$ independent of $n$?  
> **username_0**: 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.  
> **username_3**: Sorry, yes, you are absolutely right: by theorem 1, the degree is $o(n)$ as long as $\epsilon = 2^{-o(\sqrt{n})}$.  
> **username_0**: BTW is this only for AND function?? or can this be adapted to any boolean function of degree n?  
> **username_0**: @Thomas This technique seems to work for all functions of given degree. Also do you know what the minimum gap $1/2-\eta$ is from case $\deg_{1/2}(f)=0$ to $deg_\eta(f)>0$ in terms of real degree $\deg_{0}(f)$ for general boolean function $f$ in $n$ variables. Is this $1/d$?  
> **username_0**: Theorem 2 also works for parity function when we move from $e=1/2$ to $e<1/2$ (reverse of case considered here where we go from $e=0$ to $e>0$). However we know approximation degree is $\Omega(n)$ for all $e<1/2$? Your proof also works at corner case of $e=1/2$ where parity has degree $0$. However degree of $e<1/2$ is $\Omega(n)$. That is there is no open interval here.  

---

