Anders Bj"orner and Laszlo Lovasz used bounds on the Betti numbers for the complement of a real subspace arrangement called the $k$-equal arrangement to give a complexity theory lower bound that agreed, up to a scalar multiple, with the previously known upper bound in:

A. Bj"orner and L. Lovasz, Linear decision trees, subspace arrangements, and Mobius functions, Journal of the American Mathematical Society, Vol. 7, No. 3 (1994), 677--706.

The basic question addressed in their paper (along with other questions of a similar flavor) is how many pairwise comparisons of coordinates are needed to decide if a vector in ${\bf R}^n$ has $k$ coordinates all equal to each other for fixed $k$ and $n$. They observed that this is equivalent to deciding whether the vector lies on the so-called $k$-equal arrangement or in its complement, where the $k$-equal arrangement is the subspace arrangement comprised of the ${n\choose k}$ subspaces where $k$ coordinates are set equal to each other.

To this end, they gave a lower bound on the number of leaves in a linear decision tree -- a tree where one starts at the root, and each time one does a comparison of two coordinates $a_i$ and $a_j$, then one proceeds down to either the $a_i < a_j$ child or the $a_i = a_j$ child or the $a_i > a_j$ child. One reaches a leaf when no further queries are necessary to make a decision as to containment in the arrangement or its complement. The log base 3 of the number of leaves is a lower bound on the depth of the tree, i.e. on the number of queries needed in the worst case.

To get some intuition for why this bound depended fundamentally on the Betti numbers of the complement, consider the $k=2$ case -- where the number of connected components of the complement of the subspace arrangement (which in this case is a hyperplane arrangement) is an obvious lower bound on the number of leaves in any linear decision tree.

Anders Björner and László Lovász used bounds on the Betti numbers for the complement of a real subspace arrangement called the $k$-equal arrangement to give a complexity theory lower bound that agreed, up to a scalar multiple, with the previously known upper bound in:

A. Björner and L. Lovász, Linear decision trees, subspace arrangements, and Mobius functions, Journal of the American Mathematical Society, Vol. 7, No. 3 (1994), 677--706.

The basic question addressed in their paper (along with other questions of a similar flavor) is how many pairwise comparisons of coordinates are needed to decide if a vector in ${\bf R}^n$ has $k$ coordinates all equal to each other for fixed $k$ and $n$. They observed that this is equivalent to deciding whether the vector lies on the so-called $k$-equal arrangement or in its complement, where the $k$-equal arrangement is the subspace arrangement comprised of the ${n\choose k}$ subspaces where $k$ coordinates are set equal to each other.

To this end, they gave a lower bound on the number of leaves in a linear decision tree -- a tree where one starts at the root, and each time one does a comparison of two coordinates $a_i$ and $a_j$, then one proceeds down to either the $a_i < a_j$ child or the $a_i = a_j$ child or the $a_i > a_j$ child. One reaches a leaf when no further queries are necessary to make a decision as to containment in the arrangement or its complement. The log base 3 of the number of leaves is a lower bound on the depth of the tree, i.e. on the number of queries needed in the worst case.

To get some intuition for why this bound depended fundamentally on the Betti numbers of the complement, consider the $k=2$ case -- where the number of connected components of the complement of the subspace arrangement (which in this case is a hyperplane arrangement) is an obvious lower bound on the number of leaves in any linear decision tree.

Anders Bj"orner and Laszlo Lovasz used bounds on the betti numbers for the complement of a real subspace arrangement called the $k$-equal arrangement to give a complexity theory lower bound that agreed, up to a scalar multiple, with the previously known upper bound in:

A. Bj"orner and L. Lovasz, Linear decision trees, subspace arrangements, and Mobius functions, Journal of the American Mathematical Society, Vol. 7, No. 3 (1994), 677--706.

The basic question addressed in their paper (along with other questions of a similar flavor) is how many pairwise comparisons of coordinates are needed to decide if a vector in ${\bf R}^n$ has $k$ coordinates all equal to each other for fixed $k$ and $n$. They observed that this is equivalent to deciding whether the vector lies on the so-called $k$-equal arrangement or in its complement, where the $k$-equal arrangement is the subspace arrangement comprised of the ${n\choose k}$ subspaces where $k$ coordinates are set equal to each other.

To this end, they gave a lower bound on the number of leaves in a linear decision tree -- a tree where one starts at the root, and each time one does a comparison of two coordinates $a_i$ and $a_j$, then one proceeds down to either the $a_i < a_j$ child or the $a_i = a_j$ child or the $a_i > a_j$ child. Then the log base 3 of the number of leaves is a lower bound on the depth of the tree, i.e. the number of queries needed in the worst case.

To get some intuition for why this bound depended fundamentally on the Betti numbers of the complement, consider the $k=2$ case -- where the number of connected components of the complement of the subspace arrangement (which in this case is a hyperplane arrangement) is an obvious lower bound on the number of leaves in the linear decision tree.

Anders Bj"orner and Laszlo Lovasz used bounds on the Betti numbers for the complement of a real subspace arrangement called the $k$-equal arrangement to give a complexity theory lower bound that agreed, up to a scalar multiple, with the previously known upper bound in:

A. Bj"orner and L. Lovasz, Linear decision trees, subspace arrangements, and Mobius functions, Journal of the American Mathematical Society, Vol. 7, No. 3 (1994), 677--706.

The basic question addressed in their paper (along with other questions of a similar flavor) is how many pairwise comparisons of coordinates are needed to decide if a vector in ${\bf R}^n$ has $k$ coordinates all equal to each other for fixed $k$ and $n$. They observed that this is equivalent to deciding whether the vector lies on the so-called $k$-equal arrangement or in its complement, where the $k$-equal arrangement is the subspace arrangement comprised of the ${n\choose k}$ subspaces where $k$ coordinates are set equal to each other.

To this end, they gave a lower bound on the number of leaves in a linear decision tree -- a tree where one starts at the root, and each time one does a comparison of two coordinates $a_i$ and $a_j$, then one proceeds down to either the $a_i < a_j$ child or the $a_i = a_j$ child or the $a_i > a_j$ child. One reaches a leaf when no further queries are necessary to make a decision as to containment in the arrangement or its complement. The log base 3 of the number of leaves is a lower bound on the depth of the tree, i.e. on the number of queries needed in the worst case.

To get some intuition for why this bound depended fundamentally on the Betti numbers of the complement, consider the $k=2$ case -- where the number of connected components of the complement of the subspace arrangement (which in this case is a hyperplane arrangement) is an obvious lower bound on the number of leaves in any linear decision tree.