Help in geometrically understanding "Linear Decision Trees"
At each point in the linear decision tree, we branch according to whether $f(x) &gt; 0$, $f(x) = 0$ or $f(x) &lt; 0$, where $f$ is some linear functional. That means that the values of $x$ reaching some leaf are exactly those values satisfying some system of linear equations and inequalities
$$
\begin{align*}
&amp;f_1(x) = f_2(x) = \dots = f_a(x) = 0, \\
&amp;g_1(x), g_2(x), \dots, g_b(x) &gt; 0, \\
&amp;h_1(x), h_2(x), \dots, h_c(x) &lt; 0.
\end{align*}
$$
Here $f_i,g_i,h_i$ are conditions encountered along the way. (In fact we can get rid of the $h$s, but this doesn't matter.) Each of these conditions &mdash; $f_i(x) = 0$, $g_j(x) &gt; 0$ or $h_k(0) &lt; 0$ &mdash; is convex, so their intersection is convex. This means that the set of all points getting to that leaf is convex, and in particular, either empty or connected.

In order to get a lower bound for element distinctness (for example), we show that the set $\{x : \text{all components of $x$ are distinct}\}$ has many (in fact $n!$) connected components. If we take one vector each from all the connected components, then all these vectors must land at different leaves (why?), so there must be many leaves, hence the tree must be deep.