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?

  • 2
    $\begingroup$ Wikipedia is not a primary source. It cites references that it says define this model. Have you read those primary sources? Can you summarize what you've found? $\endgroup$
    – D.W.
    Oct 10 at 0:16
  • $\begingroup$ See lecture notes of Jeff Erickson. $\endgroup$ Oct 10 at 21:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy