0
$\begingroup$

$\newcommand{\R}{\mathbb{R}}$ This question is about Problem 3.16 in Ryan O'Donnell's Analysis of Boolean Functions book. The problem is stated as follows:

Let $f : \{-1,1\}^n\to\R$ and let $\epsilon>0$. Show that $f$ is $\epsilon$-concentrated on a collection $F\subseteq 2^{[n]}$ with $|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$.

Here, $\hat{||}f\hat{||}_1 := \sum_{S\subseteq [n]} |\widehat{f}(S)|$, and $f$ being $\epsilon$-concentrated on $F$ means $\sum_{S\notin F} \widehat{f}(S)^2 \leq \epsilon$. I have tried several approaches for this problem, and all seem to run into the pitfall of relating $\hat{||}f\hat{||}_1^2$ to $||f||_2$ (equivalently $\hat{||}f\hat{||}_2$ by Parseval's) in any nontrivial way. The most fruitful approach was using a probabilistic method: randomly sampling $|\widehat{f}(S)|$ uniformly over $S$, bounding the variance of this random variable, and applying Chebyshev's. But since $\mathbf{E}[|\widehat{f}(S)|]$ might be large and Chebyshev's only dictates deviation from the expectation, I don't think this approach yields the desired concentration bound. Would appreciate any hints or insight!

Edit: I was eventually able to find a solution. As a hint, start by constructing a reasonable set $F$ which trivially satisfies $|F|\leq \hat{||}f\hat{||}_1^2/\epsilon$. To prove $\epsilon$-concentration, recall the fairly simple technique used to bound $\sum \widehat{g}(S)^3$ in the analysis for the BLR test (Section 1.6 in Analysis of Boolean Functions).

$\endgroup$

2 Answers 2

0
$\begingroup$

Hint: find a random variable $X=X(S)$ such that $\mathbf{E}[X]=\hat{||}f\hat{||}_1$ where the expectation is under the spectral sample. Use this to apply Markov to find an appropriate set with Fourier mass at least $1-\epsilon$, and then argue that the size of the set must be at most the claimed cardinality.

$\endgroup$
1
  • $\begingroup$ Thanks for responding, just have a quick question. This approach seems to be assuming that the function is Boolean valued (so that total Fourier mass is equal to 1). Does scaling by $||f||_2^2$ give the same result for real-valued functions? $\endgroup$
    – Ash
    Mar 25 at 15:45
0
$\begingroup$

Here is a direct construction: $$F = \left\{S:|\hat{f}(S)|\ge \frac{\epsilon}{\hat{\|}f\hat{\|}_1}\right\}$$ And you can verify the two conditions.

$\endgroup$

Your Answer

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

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