On the computational power of Boolean decision lists
We study the computational power of decision lists over AND-functions versus threshold-circle plus circuits. AND-decision lists are a natural generalization of formulas in disjunctive or conjunctive normal form. We show that, in contrast to CNF- and DNF-formulas, there are functions with small AND-decision lists which need exponential size unbounded weight threshold-circle plus circuits. Consequently, it is questionable if the polynomial learning algorithm for DNFs of Jackson (1994), which is based on the efficient simulation of DNFs by polynomial weight threshold-circle plus circuits (Krause & Pudlak 1994), can be successfully applied to functions with small AND-decision lists. A further result is that for all k >= 1 the complexity class defined by polynomial length AC(k)(0)-decision lists lies strictly between AC(k+1)(0) and AC(k+2)(0).
decision lists ac(0) learnability lower bounds