3
$\begingroup$

In Ryan O'Donnell's book Analysis of Boolean functions, following Corollary 9.25 the following appears:

If $f\colon \{-1,1\}^n \to \{0,1\}$, and we have $\mathbb{E}[f] = \alpha$, then for any integer $k$ at most $2\ln \frac{1}{\alpha}$, we have $W^{\leq k}[f] \leq \rho^{-k}\alpha^{2(1-\rho)}$. He then deduces the following corollary:

If $\epsilon > 0$ and $k_\epsilon = 2(1-\epsilon)\ln \frac{1}{\alpha}$, then $W^{\leq k_\epsilon}[f] \leq \alpha^{\epsilon^2}$

My question is isn't this bound meaningless?

Indeed, we have

$W^{\leq k_\epsilon}[f] \leq \lVert f\rVert_2^2 = \alpha \ll \alpha^{\epsilon^2}$

$\endgroup$
  • $\begingroup$ For $0 < \epsilon < 1$, we have $a^{\epsilon^2} \ll a$, not the other way around. $\endgroup$ – Robert Andrews Oct 18 at 20:41
  • $\begingroup$ @RobertAndrews But $a<1$... $\endgroup$ – Andy Oct 18 at 21:12
  • $\begingroup$ My mistake, I completely missed that. $\endgroup$ – Robert Andrews Oct 18 at 21:32
  • 1
    $\begingroup$ @Andy Well, there is some magic number $c$ (roughly, $c\approx 1.582$) such that, setting $$k_\varepsilon = \frac{1}{c\ln(2e)}\cdot (1-\varepsilon)\ln\frac{1}{\alpha}$$ you get $$W^{\leq k_\varepsilon}[f] \leq \alpha^{1+\varepsilon-O(\varepsilon^2)}$$ $\endgroup$ – Clement C. Oct 19 at 0:05
  • 2
    $\begingroup$ The level $k$ inequality has been improved by Chin Ho Lee, Fourier Bounds and Pseudorandom Generators for Product Tests. See Lemma 10 here. $\endgroup$ – Yuval Filmus Oct 19 at 8:13
1
$\begingroup$

Just posting an answer in order to close the question.

See the helpful comments to the question which contain all the info;

  1. Yes it is vacuous, but if you use the stronger bound you get something nontrivial for large $\epsilon$, of course for fixed $k$ you also have interesting things, it's just the estimates in the book lose too much.

  2. Better bounds are known (thanks ot Yuval) : http://drops.dagstuhl.de/opus/volltexte/2019/10829/pdf/LIPIcs-CCC-2019-7.pdf

$\endgroup$
  • $\begingroup$ I'm not sure I agree with 2. As shown in my comment, the issue is not so much the tightness of the bounds used (although, of course, it cannot hurt to use the improved bound of Chin Ho Lee) as much as a bad choice of $k_\varepsilon$. Replace the leading constant $2$ in the current setting by some constant less than 1, you will get something non-vacuous. $\endgroup$ – Clement C. Oct 19 at 9:56
  • $\begingroup$ @ClementC. Yeah sure I wasn't phrasing myself well $\endgroup$ – Andy Oct 19 at 16:53

Your Answer

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

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