Some lower and upper bounds for algebraic decision trees and the separation problem
Farrokh Vatan · 2003
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 degreeor=n/2-O( square root n log /sup O(1)/n) are more powerful than trees of degree cn, with 0>