Some lower and upper bounds for algebraic decision trees and the separation problem

The complexity of computing Boolean functions with algebraic decision trees over GF(2) and R is considered. Some lower and upper bounds for algebraic decision trees of various degrees are found. It is shown that over GF(2) decision trees of degree d are more powerful than trees of degree <d. For the case of decision trees over R, it is shown that decision trees of degree ⩾n/2-O(√n log ^O(1)n) are more powerful than trees of degree cn, with 0<c<1/2