I am reading this article, and I need help with an apparently obvious proof.

The lemma (on page 5), that I want to know the proof of, is this: Let $p : \{0,1\}^N \rightarrow \mathbb{R}$ be a real multilinear polynomial of degree at most $\sqrt{N}/7$, and suppose that $|p(X)| \leq \frac{2}{3}|p(0^N)|$ for all $x \in \{0,1\}^N$ with Hamming weight 1. Then there exists an $x \in \{0,1\}^N$ such that $|p(x)| \geq 6 |p(0^n)|$.

We need the following information:

We have that a polynomial $p$ approximates a boolean function $f$ if for every $x \in \{0,1\}^n$ we have that $|p(x) - f(x)|\leq 1/3$. Then the approximate degree of $f$, $deg'(f)$ is the minimum of the degree of $p$ over all polynomials $p$ that approximate $f$

I think that Aaronson means that the lemma immediately follows from the following result (that can be found here): If $f$ is a boolean function s.t. $f(0^n) = 0$ and for $x$ with hamming weight 1 $f(x) =1$, then $deg(f) \geq \sqrt{n/2}$ and $deg'(f)\geq \sqrt{n/6}$.

So how can we proof the lemma? I am already confused that we have that " $|p(X)| \leq \frac{2}{3}|p(0^N)|$" instead of " $|p(X)| \leq \frac{1}{3}|p(0^N)|$". You can perhaps assume that $p(0^N) = 1$ and then deduce that $1-p$ cannot approximate the OR function, because the degree is too low. But I dont see how I get the rest.

  • 1
    $\begingroup$ Take $\tilde{p}$ be the symmetrized polynomial of $p$ and then you could apply Theorem 2 in the Nisan-Szegedy paper. $\endgroup$ – Willard Zhan Sep 29 '17 at 19:58

Your Answer

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

Browse other questions tagged or ask your own question.