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: Yes, thanks! Sorry for the delay in replying.Ryan O'Donnell: No, it's definitely messed up. Will fix!Ryan O'Donnell: Thanks!Ryan O'Donnell: Hi Amir. It's just a 'dummy variable'; in some sense an X's...Ryan O'Donnell: Right, or I guess I can just switch 'codimension' to 'dimens...Ryan O'Donnell: Yep, thanks!Ryan O'Donnell: Thanks, seems like I spotted this one myself too. (Not corr...