# Relation beween approximate degree of a function and its Fourier coefficient.

Consider a Boolean function $$f:\{0,1\}^n\to\{0,1\}$$.

The degree of the function $$d$$ has a clear meaning in term of its Fourier coefficients, there are no weight on coefficient of degree higher than $$d$$, i.e. $$\forall S\subseteq [1,n], \hat{f}(S) = 0$$ if $$|S| > d$$.

[edit:add] The approximate degree $$\tilde{d}$$ of a function $$f$$ is the lowest degree of a polynomial $$p$$ such that $$\max_{x\in\{0,1\}^n} |f(x) - p(x)| \leq 1/3$$. [/edit:add]

I was wondering if there is an interpretation of the approximate degree along those kind of lines. I have the intuition (maybe plain wrong) the Fourier coefficient of a function lower that its approximate degree should be small, but I cannot find any claim to sustain this intuition.

The only result I am aware of, is a paper by Sherstov, in STOC'08 (corollary 3.3.1):

Let $$f:\{0,1\}^n \to \mathbb{R}$$ with approximate degree $$\tilde{d}$$. Then there is a function $$\psi:\{0,1\}^n\to\mathbb{R}$$ such that

$$\hat{\psi}(S) = 0$$ if $$|S|<\tilde{d}$$

$$\sum_{x\in\{0,1\}^n}|\psi(x)| = 1$$

$$\sum_{x\in\{0,1\}^n} \psi(x) f(x) > 1/3$$

But the interpretation is very not clear to me since $$\psi$$ is bounded in the $$\ell_1$$ norm and not the $$\ell_2$$ norm as usually used in Fourier analysis. Also how can we have a constant overlap between $$\psi$$ and $$f$$ when $$f$$ is unbounded?

• Could you add a short definition of approximate degree of a function for those who aren't familiar with it? (There might even be different definitions in the literature based on which norm is used to quantify that two functions are close.) – Robin Kothari Jul 22 '11 at 14:37
• Hi Robin, just did it. So basically it is the $\ell_\infty$ norm. This is also the reason why the $\ell_1$ norm pops-up, since they are dual of each other. – Loïck Jul 22 '11 at 15:43
• How about considering the sum of squares of the Fourier coefficients of f−p? This must be small by Parseval’s identity. – Tsuyoshi Ito Jul 23 '11 at 21:53
• Yes, this tells us that the sum of the square of the weights of $f$ on Fourier coefficient is small. In this case 1/9. ($\sum_{S : |S| = \tilde{d}+1}^d \hat{f}(S)^2 \leq (\frac{1}{3})^2$) I am interested in the reverse property, ie that $\sum_{S:|S|=\tilde{d}} \hat{f}(S)^2$ is large. – Loïck Jul 26 '11 at 18:57
• Maybe I don't understand the question properly, but... isn't the Inner Product function (f(x,y) = (-1)^{<x,y>} where the inner product is taken over F_2) a function with very small fourier coefficients but approximate degree as large as possible? – Srikanth Aug 3 '11 at 21:57