I am trying to understand what an algebraic decision tree is but wikipedia lacks a formal definition, just an intuition. So I need to check if my understanding is correct.
From what I have read it seems that an algebraic decision tree is:
- A tree where each node has exactly 2 children.
- Each node in the tree is a polynomial function of degree at most $n$, that takes a vector of size $n$ and returns the sign of the polynomial.
- Given an input vector we evaluate the polynomial at the root node, then if the sign is positive we evaluate the polynomial of the right child otherwise that of the left.
- We do this until we hit a leaf node.
Is the above description correct?