Decision Tree Complexity and Betti Numbers

摘要

We show that any algebraic computation tree or any fixed-degree algebraic tree for solving the membership question of a compact setS⊆Rnmust have height greater thanΩ(log(βi(S)))−cnfor eachi, whereβi(S) is theith Betti number. This generalizes a well-known result by Ben-Or who proved this lower bound for the casei=0, and a recent result by Björner and Lovász who proved this lower bound for allifor linear decision trees.