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

Ryan O'Donnell: That's two more -- thank you very much!Ryan O'Donnell: Thanks!Ryan O'Donnell: Yes, I'll change "third" to "subsequent".Ryan O'Donnell: Thanks!Matt Franklin: There may be two small typos in the proof of Corollary 9.32 ...Matt Franklin: Small typo at the end of the proof of Theorem 9.28 (p. 264 i...Matt Franklin: Small typo at the end of the proof of Proposition 9.19 (p. 2...