1
$\begingroup$

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

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Thomas Jun 4 '15 at 5:09
  • 2
    $\begingroup$ 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. $\endgroup$ – Kaveh Jun 4 '15 at 5:51
  • $\begingroup$ no not bumping. I am really looking for an example. I thought may be AND might work here. $\endgroup$ – 1.. Jun 4 '15 at 9:15
  • $\begingroup$ @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. $\endgroup$ – 1.. Jun 4 '15 at 9:15
  • $\begingroup$ You are claiming that somehow from compactness degree separation happens but not proving anything rigorously. $\endgroup$ – 1.. Jun 4 '15 at 9:48
6
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Looks like a pretty good answer. Let me check carefully. $\endgroup$ – 1.. Jun 4 '15 at 17:30
  • $\begingroup$ 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? $\endgroup$ – 1.. Jun 4 '15 at 17:41
  • $\begingroup$ I may be missing something, but I don't think this proof shows that theorem 2 is true for $\tilde{\varepsilon}$ independent of $n$? $\endgroup$ – Sasho Nikolov Jun 4 '15 at 19:11
  • $\begingroup$ 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. $\endgroup$ – 1.. Jun 4 '15 at 19:14
  • $\begingroup$ Sorry, yes, you are absolutely right: by theorem 1, the degree is $o(n)$ as long as $\epsilon = 2^{-o(\sqrt{n})}$. $\endgroup$ – Sasho Nikolov Jun 4 '15 at 19:17
6
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.