10
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Robin Kothari
    Commented Jul 22, 2011 at 14:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – Loïck
    Commented Jul 22, 2011 at 15:43
  • $\begingroup$ How about considering the sum of squares of the Fourier coefficients of f−p? This must be small by Parseval’s identity. $\endgroup$
    – Tsuyoshi Ito
    Commented Jul 23, 2011 at 21:53
  • $\begingroup$ 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. $\endgroup$
    – Loïck
    Commented Jul 26, 2011 at 18:57
  • 1
    $\begingroup$ 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? $\endgroup$
    – Srikanth
    Commented Aug 3, 2011 at 21:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.