A decision tree $T$ for $f : \{-1,1\}^n \to \{-1,1\}$ can be thought of as a deterministic algorithm which, given adaptive query access to the bits of an unknown string $x \in \{-1,1\}^n$, outputs $f(x)$. E.g., to describe a natural decision tree for $f = \mathrm{Maj}_3$ in words: “Query $x_1$, then $x_2$. If they [...]

## Recent comments

Chin Ho Lee: "(The error will be proportional to \sum_i (||X_i||^3 + ||Y_...Avishay Yanay: In the equation of theorem 9, the sum limits are $S\subseteq...Avishay Yanay: #16 What is z^T?F. Mann: The Noise Stability of constant functions have NS=0, as it i...Chin Ho Lee: In Example 42, the first Sel(x_1, x_2, x_2) should be Sel(x_...jake wellens: In Ex. 31 (b), I think we should replace $1/M$ by something ...Grigory Yaroslavtsev: Nice, hope you enjoyed your visit :)