Some tips

  • You might try using analysis of Boolean functions whenever you’re faced with a problems involving Boolean strings in which both the uniform probability distribution and the Hamming graph structure play a role. More generally, the tools may still apply when studying functions on (or subsets of) product probability spaces.
  • If you’re mainly interested in unbiased functions, or subsets of volume $\frac12$, use the representation $f : \{-1,1\}^n \to \{-1,1\}$. If you’re mainly interested in subsets of small volume, use the representation $f : \{-1,1\}^n \to \{0,1\}$.
  • As for the domain, if you’re interested in the operation of adding two strings (modulo $2$), use $\mathbb{F}_2^n$. Otherwise use $\{-1,1\}^n$.
  • If you have a conjecture about Boolean functions:
    • Test it on dictators, majority, parity, tribes (and maybe recursive majority of $3$). If it’s true for these functions, it’s probably true.
    • Try to prove it by induction on $n$.
    • Try to prove it in the special case of functions on Gaussian space.
  • Try not to prove any bound on Boolean functions $f : \{-1,1\}^n \to \{-1,1\}$ that involves the parameter $n$.
  • Analytically, the only multivariate polynomials we really know how to control are degree-$1$ polynomials. Try to reduce to this case if you can.
  • Hypercontractivity is useful in two ways: (i) It lets you show that low-degree functions of independent random variables behave “reasonably”. (ii) It implies that the noisy hypercube graph is a small-set expander.
  • Almost any result about functions on the hypercube extends to the case of the $p$-biased cube, and more generally, to the case of functions on products of discrete probability spaces in which every outcome has probability at least $p$ — possibly with a dependence on $p$, though.
  • Every Boolean function consists of a junta part and Gaussian part.

5 comments to Some tips

  • Ravi Boppana

    Thanks for the tips! In the third tip (about the domain), should $\{ -1, 1 \}$ be $\{ -1, 1 \}^n$? Can you say a word about the rationale for the fifth tip (about the parameter $n$)?

    • Ryan O'Donnell

      You’re right about the third tip, thanks!

      Regarding the 5th… well of course it’s not ironclad, but one of the themes in the area is to try to work in “$\{-1,1\}^\infty$” if possible. I guess I’m mainly thinking about theorems like hypercontractivity and the like (ones proven by induction) where one might be tempted to prove weaker versions with a dependence on $n$, but where it’s possible to prove something independent of $n$.

  • Luca

    Is there an “n-free” variant (generalization?) of KKL that has more or less the same applications?

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>