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: Good catch, thank you Xi.Ryan O'Donnell: Thank you! Sorry for the delay in replying.Ryan O'Donnell: Hi Ming. Here S stands for a fixed (non-random) subset of [...Xi Wu: typo: "our definition of $\mathbf{Inf}_i[f]$ from Chapter 2....Chengyu: Ex 2.c It should be "Suppose ... is an LTF with $\textbf{E}...Ming: I confuse the notation S in Fact 1.7. I wonder that the sym...Ryan O'Donnell: Yes, thanks! Sorry for the delay in replying.