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}$

  • $\begingroup$ For $0 < \epsilon < 1$, we have $a^{\epsilon^2} \ll a$, not the other way around. $\endgroup$ Oct 18 '19 at 20:41
  • $\begingroup$ @RobertAndrews But $a<1$... $\endgroup$
    – Andy
    Oct 18 '19 at 21:12
  • $\begingroup$ My mistake, I completely missed that. $\endgroup$ Oct 18 '19 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 '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$ Oct 19 '19 at 8:13

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

  • $\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 '19 at 9:56
  • $\begingroup$ @ClementC. Yeah sure I wasn't phrasing myself well $\endgroup$
    – Andy
    Oct 19 '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.