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

jake wellens: In Ex. 31 (b), I think we should replace $1/M$ by something ...Grigory Yaroslavtsev: Nice, hope you enjoyed your visit :)Yongzhi: I think that the domain of the function g in Fact 21 should ...El Manolo: I can't figure out ex.12 b) and c) in the proposed way. Tha...R.: Is $\rho\neq 0$ required in 1(f)?R.: Typo: they introduced also introduced “tribes”Chin Ho Lee: they introduced also introduced “tribes” -> they also int...