<p>Consider a Boolean function <span class="math-container">$f:\{0,1\}^n\to\{0,1\}$</span>.</p>
<p>The degree of the function <span class="math-container">$d$</span> has a clear meaning in term of its Fourier coefficients, there are no weight on coefficient of degree higher than <span class="math-container">$d$</span>, i.e. <span class="math-container">$\forall S\subseteq [1,n], \hat{f}(S) = 0$</span> if <span class="math-container">$|S| &gt; d$</span>.</p>
<p><strong>[edit:add]</strong> The approximate degree <span class="math-container">$\tilde{d}$</span> of a function <span class="math-container">$f$</span> is the lowest degree of a polynomial <span class="math-container">$p$</span> such that <span class="math-container">$\max_{x\in\{0,1\}^n} |f(x) - p(x)| \leq 1/3$</span>.  <strong>[/edit:add]</strong></p>
<p>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.</p>
<p>The only result I am aware of, is a paper by Sherstov, in STOC'08 (corollary 3.3.1):</p>
<blockquote>
<p>Let <span class="math-container">$f:\{0,1\}^n \to \mathbb{R}$</span> with approximate degree <span class="math-container">$\tilde{d}$</span>. Then there is a function <span class="math-container">$\psi:\{0,1\}^n\to\mathbb{R}$</span> such that</p>
<p>• <span class="math-container">$\hat{\psi}(S) = 0$</span> if <span class="math-container">$|S|&lt;\tilde{d}$</span></p>
<p>• <span class="math-container">$\sum_{x\in\{0,1\}^n}|\psi(x)| = 1$</span></p>
<p>• <span class="math-container">$\sum_{x\in\{0,1\}^n} \psi(x) f(x) &gt; 1/3$</span></p>
</blockquote>
<p>But the interpretation is very not clear to me since <span class="math-container">$\psi$</span> is bounded in the <span class="math-container">$\ell_1$</span> norm and not the <span class="math-container">$\ell_2$</span> norm as usually used in Fourier analysis. Also how can we have a constant overlap between <span class="math-container">$\psi$</span> and <span class="math-container">$f$</span> when <span class="math-container">$f$</span> is unbounded?</p>

CC BY-SA 3.0
2011-07-22T14:37:21.277Z
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
CC BY-SA 3.0
2011-07-22T15:43:07.383Z
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
CC BY-SA 3.0
2011-07-23T21:53:29.670Z
How about considering the sum of squares of the Fourier coefficients of f−p?  This must be small by Parseval’s identity.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-26T18:57:42.533Z
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
CC BY-SA 3.0
2011-08-03T21:57:06.537Z
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
CC BY-SA 3.0
2012-10-04T04:17:42.737Z
see also [Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?](http://cstheory.stackexchange.com/questions/12769/are-all-the-functions-whose-fourier-weight-is-concentrated-on-the-small-sized-se)
vzn
<cc.complexity-theory><co.combinatorics><boolean-functions><fourier-analysis>
Relation beween approximate degree of a function and its Fourier coefficient.
Loïck
# Relation beween approximate degree of a function and its Fourier coefficient.

(Asked by: username_0 on 2011-07-22)

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?

**Tags:** cc.complexity-theory, co.combinatorics, boolean-functions, fourier-analysis

> **Comments:**
> **username_1**: 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.)  
> **username_0**: 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.  
> **username_2**: How about considering the sum of squares of the Fourier coefficients of f−p?  This must be small by Parseval’s identity.  
> **username_0**: 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.  
> **username_3**: 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?  
> **username_4**: see also [Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?](http://cstheory.stackexchange.com/questions/12769/are-all-the-functions-whose-fourier-weight-is-concentrated-on-the-small-sized-se)  

---

## 0 answers

