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

Matt Franklin: Maybe two small typos in the proof of Corollary 11.67 (p. 36...Ryan O'Donnell: I see your point, although in some sense this distinction be...Ryan O'Donnell: Thank you!Ryan O'Donnell: Yep, thanks!Ryan O'Donnell: Great catch, thanks!Matt Franklin: Maybe two small typos in last sentence before Borell's Isope...Matt Franklin: maybe small typo in Remark 11.11 (p. 328 in book): $z \tild...